1 条题解

  • 0
    @ 2026-2-11 2:29:08
    #include<bits/stdc++.h>//scy教学代码(初学者用)
    using namespace std;
    struct node
    {
        int a[3][5],dep,kt;
        char cz[30];
    };
    deque<node>Q;map<int,bool>v;
    int kt(node no)
    {
        int s=0;for(int i=1;i<=2;i++)for(int j=1;j<=4;j++)s=s*10+no.a[i][j];
        return s;
    }
    node AA(node tno)
    {
        node no=tno;
    	for(int i=1;i<=4;i++)swap(no.a[1][i],no.a[2][i]);
    
        no.dep++;no.cz[no.dep]='A';no.kt=kt(no);
        return no;
    }
    node BB(node tno)
    {
        node no=tno;
    	for(int j=4;j>1;j--)swap(no.a[1][j],no.a[1][j-1]),swap(no.a[2][j],no.a[2][j-1]);
    
    	no.dep++;no.cz[no.dep]='B';no.kt=kt(no);
        return no;
    }
    node CC(node tno)
    {
        node no=tno;
        no.a[1][2]=tno.a[2][2];no.a[1][3]=tno.a[1][2];
        no.a[2][2]=tno.a[2][3];no.a[2][3]=tno.a[1][3];
    
        no.dep++;no.cz[no.dep]='C';no.kt=kt(no);
        return no;
    }
    int main()
    {
        node stno,edno;
        for(int i=1;i<=2;i++)for(int j=1;j<=4;j++)stno.a[i][j]=(i-1)*4+j;
    	for(int j=1;j<=2;j++) swap(stno.a[2][j],stno.a[2][4-j+1]);
    	stno.dep=0;stno.kt=kt(stno);
    	
        for(int i=1;i<=2;i++)for(int j=1;j<=4;j++)scanf("%d",&edno.a[i][j]);
    	for(int j=1;j<=2;j++) swap(edno.a[2][j],edno.a[2][4-j+1]);	
    	edno.kt=kt(edno);
    	
    	if(stno.kt==edno.kt){printf("0\n");return 0;}	
    	
        v.clear();v[stno.kt]=1;
        Q.clear();Q.push_back(stno);
        bool bk=0;
        while(!Q.empty())
        {
        	node no;
        	for(int i=1;i<=3;i++)
        	{
        		if(i==1)      no=AA(Q.front());
        		else if(i==2) no=BB(Q.front());
        		else          no=CC(Q.front());
        		if(v[no.kt]==0) {
    				v[no.kt]=1;
    				Q.push_back(no);
    				if(no.kt==edno.kt){bk=1;break;}
    			}
    		}
    		Q.pop_front();
    		if(bk==1) break;
    	}
    	
        printf("%d\n",Q.back().dep);
        if(Q.back().dep>0)
    	{
    		for(int i=1;i<=Q.back().dep;i++) printf("%c",Q.back().cz[i]);
        	printf("\n");
        }
        return 0;
    }
    
    • 1

    B16【宽搜】[IOI 1996 / USACO3.2] 魔板 Magic Squares

    信息

    ID
    88
    时间
    1000ms
    内存
    128MiB
    难度
    8
    标签
    递交数
    479
    已通过
    87
    上传者