[ZJ] a815. 2013高雄市能力競賽高中組 6. 蜜蜂飛行

#include<stdio.h>
#include<string.h>
char s[305][305];
int v[305][305];
int d[6][2]={{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0}};
void dfs(int x,int y,int t,char c){
    if(v[x][y]) return;
    v[x][y]=t;
    int i;
    for(i=0;i<6;i++){
        if(s[x+d[i][0]][y+d[i][1]]==c)
            dfs(x+d[i][0],y+d[i][1],t,c);
    }
}
int main(){
    int t,n,m,i,j,k,a,b,C=0;
    scanf("%d",&t);
    while(t--){
        C++;
        memset(s,0,sizeof(s));
        memset(v,0,sizeof(v));
        scanf("%d%d",&n,&m);
        for(i=1;i<=n;i++)
            scanf("%s",&s[i][1]);
        dfs(1,1,1,'.');
        if(v[n][m]!=1){
            puts("0");
            goto go;
        }
        for(i=1;i<=n;i++){
            if(s[i][1]=='O')
                dfs(i,1,2,'O');
            if(s[i][m]=='O')
                dfs(i,m,3,'O');
        }
        for(i=1;i<=m;i++){
            if(s[1][i]=='O')
                dfs(1,i,3,'O');
            if(s[n][i]=='O')
                dfs(n,i,2,'O');
        }
        /*for(i=1;i<=n;i++){
            for(j=1;j<=m;j++)
                printf("%d ",v[i][j]);
            puts("");
        }*/
        for(i=1;i<=n;i++){
            for(j=1;j<=m;j++){
                if(i==1 && j==1) continue;
                if(i==n && j==m) continue;
                a=0,b=0;
                if(i==1 || j==m) a=1;
                for(k=0;k<6;k++)
                    if(v[i+d[k][0]][j+d[k][1]]==3) a=1;
                if(i==n || j==1) b=1;
                for(k=0;k<6;k++)
                    if(v[i+d[k][0]][j+d[k][1]]==2) b=1;
                if(a+b==2){
                    puts("1");
                    goto go;
                }
            }
        }
        puts("2");
        go:;
    }
}