一个n*m的矩阵，Vasya想要从矩阵矩阵的（1,1)(左上角）走到（n,m)(右下角），矩阵中有一些格不能走，一次只能向下或向右。现在你可以使一些格变得不能走来阻止他走到，问最少改变几个格。 (3<=n*m<=1000000)
直接把起点或终点围住不就好了吗。这是我第一发WA，然后发现我好傻呀，矩阵中本来就有一些障碍。
把矩阵按行加列分层，即，
则从左上角到右下角的路径一定经过每一层的至少一个格，那么我从起点bfs一遍统计出每层能到达的格分别有多少个，我只需要把其中一层能到达的全部格都变成障碍就好，那一层需要变得少就变哪一层。于是我又WA了一发。
上述想法还有一个漏洞，就是有可能这一层的这个格是可以到达的，但是从它又到不了（n，m）（例如，下图的样例），这一层就完全可以不用把这个格变为障碍，但是统计能到达格的时候又记录了它。出现这样的情况只能因为走到有些格就在已无法到达终点了，那么这些点无异于障碍，因此加一个预处理把这样的点都变成障碍就好（注意要从终点向前找）。
1 #include<bits/stdc++.h> 2 3 using namespace std; 4 5 int n,m; 6 char s[1000006]; 7 int cnt[1000006],dis[1000006]; 8 queue<int> 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<n+m;i++) 50 { 51 ans=min(ans,cnt[i]); 52 } 53 cout<<ans<<endl; 54 return 0; 55 }
原文：https://www.cnblogs.com/LiqgNonqfu/p/11462670.html