刚开始按\(wqy\)的思路写，提交了\(n\)遍也没过。。。

学到了压成一维。

还是梳理梳理错因吧：

• 1.对每个井号进行\(bfs\)，会超时(我真是太傻逼了)。
• 2.对于\(0\)的情况，一个点如果之前被标记过，并且之前被标记的和现在要标记的值不一样，答案才会是\(0\)。
• 3.在初始化的时候也要判断2中的情况（之前被标记过），因为有一行（或者一列）的情况。
• 4.\(wqy\)说的四周是周围\(8\)个格子。
• 5.对于一个点，如果进队了要标记，防止进队很多次。（\(test\,10\)

• 6.关于出队清不清标记？？？(\(test\,18\)

  改成出队不清标记，进队是没有标记才进。才同时过了10,18

先贴一份没有\(AC\)的代码：

#include
    
     #include
     
      #include
      
       using namespace std;const int N = 2e6+5;int n,m,a[N],id[N],qx[N],qy[N],l=1,r;int dx[10]={0,0,1,-1,0,-1,1,-1,1};int dy[10]={0,1,0,0,-1,-1,1,1,-1};bool book[N],flag=0;char c;/*int bft(int x,int y){    memset(book,0,sizeof(book));    qx[1]=x; qy[1]=y;    l=r=1;    bool flag1=0,flag2=0;    if(x==n||y==1) flag1=1;    if(x==1||y==m) flag2=1;    while(l<=r)    {        if(flag1&&flag2) break;//      if(flag3&&t) return 5;        int xt=qx[l],yt=qy[l],xx,yy;        ++l;        for(int i=1;i<=8;i++)        {//          if(t&&i==3) break;            xx=xt+dx[i],yy=yt+dy[i];            if(xx>n||yy>m) continue;            if(xx<1||yy<1) continue;            if(a[(xx-1)*m+yy]==0&&!book[(xx-1)*m+yy])            {                qx[++r]=xx; qy[r]=yy;                book[(xx-1)*m+yy]=1;                if(xx==n||yy==1) flag1=1;                if(xx==1||yy==m) flag2=1;//              if(xx==n&&yy==m) flag3=1;            }        }    }//  if(flag3&&t) return 5;    if(flag1&&flag2) return 3;    if(flag1) return 1;    if(flag2) return 2;    return 0;}*/void bfs(){    while(l<=r)    {        int xt=qx[l],yt=qy[l],xx,yy;        ++l; //      book[(xt-1)*m+yt]=0;        for(int i=1;i<=8;i++)        {            xx=xt+dx[i],yy=yt+dy[i];            if(xx<1||xx>n) continue;            if(yy<1||yy>m) continue;            if(!a[(xx-1)*m+yy])            {                if(id[(xx-1)*m+yy]!=0&&id[(xx-1)*m+yy]!=id[(xt-1)*m+yt])                 { flag=1; return ; }//              { flag=1; return ;}                id[(xx-1)*m+yy]=id[(xt-1)*m+yt];//              printf("%d %d %d\n",r,xx,yy);                if(!book[(xx-1)*m+yy]) qx[++r]=xx,qy[r]=yy;                book[(xx-1)*m+yy]=1;            }        }    }//  cout<
       
        <<"*******"<
        
         >c;        if(c=='.') a[(i-1)*m+j]=1;        else a[(i-1)*m+j]=0;     }     // 1 左下 2 右上       for(int i=1;i<=n;i++)     {        if(a[(i-1)*m+1]==0&&id[(i-1)*m+1]==2) { printf("0\n"); return 0; }        if(a[(i-1)*m+1]==0) { id[(i-1)*m+1]=1,qx[++r]=i,qy[r]=1,book[(i-1)*m+1]=1;}                if(a[(i-1)*m+m]==0&&id[i*m]==1) { printf("0\n"); return 0; }        if(a[(i-1)*m+m]==0) { id[i*m]=2,qx[++r]=i,qy[r]=m,book[i*m]=1;}     }    for(int i=1;i<=m;i++)    {        if(a[i]==0&&id[i]==1) { printf("0\n"); return 0; }        if(a[i]==0) { id[i]=2,qx[++r]=1,qy[r]=i,book[i]=1;}                if(a[(n-1)*m+i]==0&&id[(n-1)*m+i]==2) { printf("0\n"); return 0; }        if(a[(n-1)*m+i]==0)  { id[(n-1)*m+i]=1,qx[++r]=n,qy[r]=i,book[(n-1)*m+i]=1; }    }/*  for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)         cout<
         
          <<"*"; cout<
          
           n) continue; if(j+dy[k]<=0||j+dy[k]>m) continue; if(id[(i+dx[k]-1)*m+j+dy[k]]==1) a1=1; if(id[(i+dx[k]-1)*m+j+dy[k]]==2) a2=1; } if(a1==1&&a2==1) { printf("0\n"); return 0;} if(a1==1) id[(i-1)*m+j]=1; if(a2==1) id[(i-1)*m+j]=2; }*/ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)// if(a[(i-1)*m+j]==1) { if(i==1&&j==1) continue; if(i==n&&j==m) continue; a1=0,a2=0; if(i==n||j==1) a1=1; if(i==1||j==m) a2=1; for(int k=1;k<=8;k++) { if(i+dx[k]<=0||i+dx[k]>n) continue; if(j+dy[k]<=0||j+dy[k]>m) continue; if(id[(i+dx[k]-1)*m+j+dy[k]]==1) a1=1; if(id[(i+dx[k]-1)*m+j+dy[k]]==2) a2=1; } if(a1&&a2) { if(a[(i-1)*m+j]==0) { printf("0\n"); return 0; } else { printf("1\n"); return 0; } } } printf("2\n"); return 0;}
          
         
        
       
      
     
    

\(Dyj\)太神辣！！！

思路：

先判断0的情况。

对于剩下两种情况：

1.找一条最靠右，或最靠下的路径，把它全部标记上，再在标记后的新矩阵中找是否有从\(1,1\)到\(n,m\)的路径，如果有，答案为2，如果没有，答案为1.

2.如果答案为1，那么所有可行的路径必然经过同一个点（该标记的点，记为\(w\)），对于可行路径中，交点最少的两条路径一定是最靠右的一条和最靠下的一条。如果这两条路径有交点，那么答案为1，否则为2。

对1的感性证明：

如果答案为1的话，标记一条路径，那么\(w\)一定会被标记。但是标记任意一条不行，这样会把应该是2的答案判成1。

为什么呢？

因为标记一整条路径的话，除了\(w\)点是应该标记的，还会多标记好多点。假如其中某一个点是某一条可以不经过\(w\)点到\(n,m\)的路径必须经过的点的话，就会出错。

还是画个样例吧：

如果标记了红色的路径，就会错判为答案是1。

但是标记最右，或最下的路径，就不会出现这种情况。（感性理解吧 ）

不得不再说一遍，\(Dyj\)太强了。

按刁神的思路，我一直写\(T\)。

\(dfs\)时先向右走，再向下走。既然这样\(T\)的话，能不能每次只向一个方向走，反正找到一条路径就可以了嘛。

但是，这样不行。

原因：如果一个点能向右走，但是向右走几个格之后就没路了，所以在这个格应该向下走，但是已经向右走过了，所以向下的搜不到了。

刁神的神奇做法：

第一遍判情况0时的\(bfs\)对每个点记录一个相当于\(dis\)的值，每个点的\(dis\)都等于从它转移过来的那个点的\(dis+1\)。然后\(dfs\)找路径标记的时候，从\(n,m\)向左上走，假如接下来要搜的点的\(dis\)等于当前点的\(dis-1\)，那么才搜，否则不搜。

推荐大佬的

一样没有\(AC\)的代码：

#include
    
     #include
     
      #include
      
       using namespace std;const int N = 1e6+10;int n,m,a[N],qx[N],qy[N],l=1,r;bool book[N],flag;char c;void work(){/*  for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)         cout<
       
        <<"*";        cout<
        
         n||x<1) return ;    if(y<1||y>m) return ;    if(a[(x-1)*m+y+1]==1&&y+1<=m)      { book[(x-1)*m+y+1]=1; dfs(x,y+1); book[(x-1)*m+y+1]=0;}    if(a[x*m+y]==1&&x+1<=n)      { book[x*m+y]=1; dfs(x+1,y); book[x*m+y]=0;}}int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++)     for(int j=1;j<=m;j++)     {        cin>>c;        if(c=='.') a[(i-1)*m+j]=1;     }    book[1]=1;    dfs(1,1);    if(flag==0) printf("0\n");    return 0;}