1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88
| #include<stdio.h> #include<cstring> #include<iostream> using namespace std; int T,n; int a[120][120]; int col[120][120]; int ck1(int x,int y){ return x-1>0&&a[x-1][y]; } int ck2(int x,int y){ return x-1>0&&y+1<=n&&a[x-1][y+1]; } int ck3(int x,int y){ return y-1>0&&a[x][y-1]; } int t=0; int f[10][10]={{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0}}; bool check(int x,int y){ for(int i=0;i<6;i++){ int xx=x+f[i][0],yy=y+f[i][1]; if(xx<1||yy<1||xx>n||yy>n||!a[xx][yy]) continue; if(col[x][y]==col[xx][yy]) return false; } return true; } void dfs(int x,int y,int c){ if(t) return; col[x][y]=c; if(!check(x,y)){ t=1; return; } for(int i=0;i<6;i++){ int xx=x+f[i][0],yy=y+f[i][1]; if(xx<1||yy<1||xx>n||yy>n||col[xx][yy]||!a[xx][yy]) continue; dfs(x+f[i][0],y+f[i][1],c^3); } } int main(){ scanf("%d",&T); while(T--){ t=0; memset(col,0,sizeof(col)); scanf("%d",&n); char s[60]; int fg=0; for(int i=1;i<=n;i++){ scanf("%s",s); for(int j=1;j<=n;j++){ if(s[j-1]=='X'){ a[i][j]=1; fg=1; } else a[i][j]=0; } } if(!fg){ printf("0\n"); continue; } fg=1; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(a[i][j]==0) continue; int cur=ck1(i,j)|ck2(i,j)|ck3(i,j); if(cur>0) fg=0; } } if(fg){ printf("1\n"); continue; } for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ if(a[i][j]&&!col[i][j]) dfs(i,j,1); } } if(!t){ printf("2\n"); } else{ printf("3\n"); } } return 0; }
|