# include<stdio.h>
# include<string.h>
# define MAX 25
struct node{
int top,bottom,right,left;
};
node square[MAX],iTable[MAX];
int n,q;
int iCount[25];
bool DFS(int pos){
if(pos == n*n) return true;
else{
int row = pos / n;
int col = pos % n;
for(int i=0;i<q;i++){
if(iCount[i] == 0) continue;
if(row != 0 )
if(square[i].top != iTable[pos-n].bottom) continue;
if(col != 0)
if(square[i].left != iTable[pos-1].right) continue;
iTable[pos] = square[i];
iCount[i]--;
if(DFS(pos+1)) return true;
iCount[i]++;
}
}
return false;
}
int main(){
freopen("in.txt","r",stdin);
int Case = 0,i,j;
while(~scanf("%d",&n) && n != 0){
memset(iCount,0,sizeof(iCount));
int top,bottom,right,left;
q = 0;
for(i=0;i<n*n;i++){
scanf("%d %d %d %d",&top,&right,&bottom,&left);
for(j=0;j<q;j++){
if(square[j].top == top && square[j].right == right
&&square[j].bottom == bottom && square[j].right == right){
iCount[j] ++;
break;
}
}
if(j == q){
square[j].top = top,square[j].bottom = bottom;
square[j].right = right,square[j].left = left;
iCount[q++]++;
}
}
Case++;
if(Case > 1) printf("\n");
if(DFS(0)) printf("Game %d:Possible\n",Case);
else printf("Game %d:Impossible\n",Case);
}
return 0;
}
找了3天都没找出错来
# include<string.h>
# define MAX 25
struct node{
int top,bottom,right,left;
};
node square[MAX],iTable[MAX];
int n,q;
int iCount[25];
bool DFS(int pos){
if(pos == n*n) return true;
else{
int row = pos / n;
int col = pos % n;
for(int i=0;i<q;i++){
if(iCount[i] == 0) continue;
if(row != 0 )
if(square[i].top != iTable[pos-n].bottom) continue;
if(col != 0)
if(square[i].left != iTable[pos-1].right) continue;
iTable[pos] = square[i];
iCount[i]--;
if(DFS(pos+1)) return true;
iCount[i]++;
}
}
return false;
}
int main(){
freopen("in.txt","r",stdin);
int Case = 0,i,j;
while(~scanf("%d",&n) && n != 0){
memset(iCount,0,sizeof(iCount));
int top,bottom,right,left;
q = 0;
for(i=0;i<n*n;i++){
scanf("%d %d %d %d",&top,&right,&bottom,&left);
for(j=0;j<q;j++){
if(square[j].top == top && square[j].right == right
&&square[j].bottom == bottom && square[j].right == right){
iCount[j] ++;
break;
}
}
if(j == q){
square[j].top = top,square[j].bottom = bottom;
square[j].right = right,square[j].left = left;
iCount[q++]++;
}
}
Case++;
if(Case > 1) printf("\n");
if(DFS(0)) printf("Game %d:Possible\n",Case);
else printf("Game %d:Impossible\n",Case);
}
return 0;
}
找了3天都没找出错来