为什么死循环?
查看原帖
为什么死循环?
873417
Istruggle楼主2024/6/27 14:37
#include<bits/stdc++.h>
using namespace std;
int mp[5][5][5][5],cnt=0;
int f1[11][11],f2[11][11];
int ans=0,s[5][5];
struct node{
	int x[5][5];
};
vector<node> a[5][5]; 
int score[10][10]={
    {0,0,0,0,0,0,0,0,0,0},
    {0,6,6,6,6,6,6,6,6,6},
    {0,6,7,7,7,7,7,7,7,6},
    {0,6,7,8,8,8,8,8,7,6},
    {0,6,7,8,9,9,9,8,7,6},
    {0,6,7,8,9,10,9,8,7,6},
    {0,6,7,8,9,9,9,8,7,6},
    {0,6,7,8,8,8,8,8,7,6},
    {0,6,7,7,7,7,7,7,7,6},
    {0,6,6,6,6,6,6,6,6,6},};
void dfs(int X,int Y){
	//cout<<x<<" "<<y<<endl;
	if(X==4){
		int tmp=0;
		for(int i = 1;i<=3;i++)
		for(int j = 1;j<=3;j++)
		for(int k = 1;k<=3;k++)
		for(int l = 1;l<=3;l++){
			int rx=3*(i-1)+k,ry=3*(j-1)+l;
			tmp+=score[rx][ry]*a[i][j][s[i][j]].x[k][l];
		}
		ans=max(ans,tmp);
		return;
	}
	for(int i = 0;i<a[X][Y].size();i++){
		int f=1;
		for(int k = 1;k<=3;k++){
			for(int l = 1;l<=3;l++){
	    		int rx=3*(X-1)+k,ry=3*(Y-1)+l;
	    		if(f1[rx][a[X][Y][i].x[k][l]]||f2[ry][a[X][Y][i].x[k][l]]){
	    			f=0; break;
	    		}
	    	}
	    	if(!f) break;
	 	}
	 	if(f){ 
	 		s[X][Y]=i;
	 		for(int k = 1;k<=3;k++)
			for(int l = 1;l<=3;l++){
	    		int rx=3*(X-1)+k,ry=3*(Y-1)+l;
	    		f1[rx][a[X][Y][i].x[k][l]]=1;
				f2[ry][a[X][Y][i].x[k][l]]=1;	
	    	}
	    	if(Y==3)
	    	dfs(X+1,1);
	    	else dfs(X,Y+1);
	    	for(int k = 1;k<=3;k++)
			for(int l = 1;l<=3;l++){
	    		int rx=3*(X-1)+k,ry=3*(Y-1)+l;
	    		f1[rx][a[X][Y][i].x[k][l]]=0;
				f2[ry][a[X][Y][i].x[k][l]]=0;	
	    	}
		}
	}
}
int main(){
	for(int i = 1;i<=9;i++)
	for(int j = 1;j<=9;j++){
		int x=ceil(i/3.0);
		int y=ceil(j/3.0);
		scanf("%d",&mp[x][y][i-3*(x-1)][j-3*(y-1)]);
	}
	int num[9]={1,2,3,4,5,6,7,8,9};  
    do{ // cout<<"!";
        int tmp[5][5];
        tmp[1][1]=num[0]; tmp[1][2]=num[1]; tmp[1][3]=num[2];
        tmp[2][1]=num[3]; tmp[2][2]=num[4]; tmp[2][3]=num[5];
        tmp[3][1]=num[6]; tmp[3][2]=num[7]; tmp[3][3]=num[8];
        for(int i = 1;i<=3;i++)
        for(int j = 1;j<=3;j++){
        	int f=1;
        	for(int k = 1;k<=3;k++){
        		for(int l = 1;l<=3;l++){
                 	if(mp[i][j][k][l]!=0&&mp[i][j][k][l]!=tmp[k][l]){
                 		f=0;
         	        	break;
		        	}
	        	}
	        	if(!f) break;
			}
	    	if(f){
	    		node r;
	    		r.x[1][1]=tmp[1][1]; r.x[1][2]=tmp[1][2]; r.x[1][3]=tmp[1][3];
	    		r.x[2][1]=tmp[2][1]; r.x[2][2]=tmp[2][2]; r.x[2][3]=tmp[2][3];
	    		r.x[3][1]=tmp[3][1]; r.x[3][2]=tmp[3][2]; r.x[3][3]=tmp[3][3];
	    		a[i][j].push_back(r);
			}
		}
    }while(next_permutation(num,num+9));  
    dfs(1,1);
    printf("%d",ans);
} 
2024/6/27 14:37
加载中...