题目大意

　　一个n*m的矩阵，Vasya想要从矩阵矩阵的（1,1)(左上角）走到（n,m)(右下角），矩阵中有一些格不能走，一次只能向下或向右。现在你可以使一些格变得不能走来阻止他走到，问最少改变几个格。 (3<=n*m<=1000000)

思路

　　把矩阵按行加列分层，即，

                                                                          

 

　　则从左上角到右下角的路径一定经过每一层的至少一个格，那么我从起点bfs一遍统计出每层能到达的格分别有多少个，我只需要把其中一层能到达的全部格都变成障碍就好，那一层需要变得少就变哪一层。于是我又WA了一发。

　　上述想法还有一个漏洞，就是有可能这一层的这个格是可以到达的，但是从它又到不了（n，m）（例如，下图的样例），这一层就完全可以不用把这个格变为障碍，但是统计能到达格的时候又记录了它。出现这样的情况只能因为走到有些格就在已无法到达终点了，那么这些点无异于障碍，因此加一个预处理把这样的点都变成障碍就好（注意要从终点向前找）。

                                                                    

代码

1 #include
     
       2  3 using namespace std; 4  5 int n,m; 6 char s[1000006]; 7 int cnt[1000006],dis[1000006]; 8 queue
      
        q; 9 10 int main()11 {12     scanf("%d%d",&n,&m);13     char ch=getchar();14     for(int i=1;i<=n;i++)15     {16         while(ch!='.'&&ch!='#')ch=getchar();17         for(int j=1;j<=m;j++)18         {19             s[(i-1)*m+j]=ch;20             ch=getchar();21         }22     }23     for(int i=m*n-1;i>1;i--)//预处理 24     {25         int r=(i+m-1)/m,c=i%m;26         if(c==0)c=m;27         if(c+1>m||(c+1<=m&&s[(r-1)*m+c+1]=='#'))28             if(r+1>n||(r+1<=n&&s[r*m+c]=='#'))s[i]='#';29     }30     q.push(1);31     dis[1]=2;32     while(!q.empty())//bfs 33     {34         int dang=q.front();q.pop();cnt[dis[dang]]++;35         int r=(dang+m-1)/m,c=dang%m;36         if(c==0)c=m;37         if(c+1<=m&&s[(r-1)*m+c+1]=='.'&&dis[(r-1)*m+c+1]==0)38         {39             dis[(r-1)*m+c+1]=dis[dang]+1;40             q.push((r-1)*m+c+1);41         }42         if(r+1<=n&&s[r*m+c]=='.'&&dis[r*m+c]==0)43         {44             dis[r*m+c]=dis[dang]+1;45             q.push(r*m+c);46         }47     }48     int ans=2;49     for(int i=3;i