CF1214D Treasure Island

题目链接

题目大意

　　一个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 }