思路难以发现但易于理解的题。
题意
从 \(N\times M\) 的网格中，找尽可能多的路径，要求：
- 起点在左上角，终点在右下角，路径只能向右和向下延伸
- 两条路径不能相互穿过
- 相邻两条路径之间必须包含有洞
求出路径数量的最大值 \(K\)。
思路
题面为路径定义了“编号”，描述不是很好理解，所以画一张图：
此时可以看出，路径的“编号”即为从右上到左下的顺序，对应到这张图中就是黑、黄、红、蓝、绿。
可以发现，最优情况即，对于从右上到左下的每一个洞，都分别有一条路径将其围在与上一条路径形成的空隙中，答案为洞的个数 \(+1\)。
但因为路径只能向右和向下延伸，所以有一些实际无法通过的空位需要特殊考虑。
第一种情况，两个洞呈右上左下排列，即：
.#
#.
不难发现这时两个空位均无法被路径经过。
第二种情况，边界：
----
.#..
在上边界的洞，右侧空位无法通过。
|.
|#
|.
|.
在左边界的洞，下侧空位无法通过。
.#..
----
在下边界的洞，左侧空位无法通过。
.|
#|
.|
.|
在右边界的洞，上侧空位无法通过。
对于这两种特殊情况，我们可以把无法通过的空位都替换成洞来处理。这样处理的好处在于，如果遇到连锁情况，如：
..#
##.
或
----
.#..
.#..
.#..
我们可以通过再去判断新替换的洞的情况，处理连锁无法通过的问题。
这启示我们使用 BFS 来把洞补全，完成对特殊情况的处理。
随后，考虑每一个洞是否可以被两个路径围起来。八连通的洞可被视为一个大洞，因为中间没有空位供路径穿过。同时在边界的洞不能计入洞的总数，因为没有路径可以从边界外经过。最后的答案 \(K\) 即为此时洞的总数 \(+1\)。
注意以下两种情况：
----
|..#
|..#
|###
左上角起点在处理特殊情况时会被替换成洞。
###|
#..|
#..|
----
右下角终点在处理特殊情况时会被替换成洞。
这两种情况答案都是 \(0\)，需要特判输出。
代码
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
const int N=2010;
const int dx[9]={0,1,0,-1,0,-1,1,1,-1};
const int dy[9]={0,0,1,0,-1,-1,-1,1,1};
struct Node{int x,y;
};
int n,m,ans;
int a[N][N];
bool vis[N][N];
queue<Node>q,r;
bool bfs(int x,int y){bool flag=1;r.push((Node){x,y});a[x][y]=0;while(!r.empty()){Node f=r.front();int xx=f.x,yy=f.y;if(xx==1||yy==1||xx==n||yy==m) flag=0;r.pop();for(int i=1;i<=8;i++){int qx=xx+dx[i],qy=yy+dy[i];if(qx>=1&&qx<=n&&qy>=1&&qy<=m){if(a[qx][qy]){r.push((Node){qx,qy});a[qx][qy]=0;} }}}return flag;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){char c;cin>>c;if(c=='#'){a[i][j]=1;q.push((Node){i,j});vis[i][j]=1;} }}while(!q.empty()){//一次bfs，处理特殊情况Node f=q.front();int x=f.x,y=f.y;q.pop();if(x==1&&y<m){if(!vis[x][y+1]){a[x][y+1]=1;q.push((Node){x,y+1});vis[x][y+1]=1;}}if(y==1&&x<n){if(!vis[x+1][y]){a[x+1][y]=1;q.push((Node){x+1,y});vis[x+1][y]=1;}}if(x==n&&y>1){if(!vis[x][y-1]){a[x][y-1]=1;q.push((Node){x,y-1});vis[x][y-1]=1;}}if(y==m&&x>1){if(!vis[x-1][y]){a[x-1][y]=1;q.push((Node){x-1,y});vis[x-1][y]=1;}}if(a[x+1][y-1]){if(!vis[x][y-1]){a[x][y-1]=1;q.push((Node){x,y-1});vis[x][y-1]=1;}if(!vis[x+1][y]){a[x+1][y]=1;q.push((Node){x+1,y});vis[x+1][y]=1;}}if(a[x-1][y+1]){if(!vis[x-1][y]){a[x-1][y]=1;q.push((Node){x-1,y});vis[x-1][y]=1;}if(!vis[x][y+1]){a[x][y+1]=1;q.push((Node){x,y+1});vis[x][y+1]=1;}}}if(a[1][1]||a[n][m]){//特判起点终点为洞的情况printf("0\n");return 0;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(a[i][j]){if(bfs(i,j)) ans++;//第二次bfs，搜连通块和判边界} }}printf("%d\n",ans+1);return 0;
}