1 条题解

  • 0
    @ 2023-5-30 19:53:55

    C++ :

    #include<bits/stdc++.h>
    using namespace std;
    int n,w,t,dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
    map<int,int>ans;
    queue<int>q;
    int main(){
    	cin>>n;
    	ans[n]=0;
    	q.push(n);
    	while(!q.empty()){
    		w=q.front();q.pop();
    		t=w;
    		if(t==255) cout<<ans[t];
    		int a[4][4],sum=15;
    		while(sum>=0){
    			a[sum/4][sum%4]=t%2;
    			t/=2,sum--;
    		}
    		for(int i=0;i<4;i++){
    			for(int j=0;j<4;j++){
    				for(int k=0;k<4;k++){
    					int tx=i+dx[k],ty=j+dy[k],len=0;
    					if(tx<0||ty<0||tx>=4||ty>=4) continue;
    					if(a[i][j]==a[tx][ty])	continue;
    					swap(a[i][j],a[tx][ty]);
    					for(int h=0;h<4;h++){
    						for(int l=0;l<4;l++) len=len*2+a[h][l];}
    					if(ans.count(len)==false){
    						ans[len]=ans[w]+1;
    						q.push(len);
    					}
    					swap(a[i][j],a[tx][ty]);
    				}
    			}
    		}
    	}
    	return 0;
    }
    
    • 1

    信息

    ID
    707
    时间
    1000ms
    内存
    128MiB
    难度
    3
    标签
    递交数
    29
    已通过
    12
    上传者