题目

题目描述
小 $C$ 喜欢作画, 尤其喜欢仅使用黑白两色作画。黑白的不一定是遗照。

画布可以看成 $r\times c$ 的单元格矩阵。现在小 $C$ 构思好了他的画，准备动笔。初始时画布是全白的，他每一次下笔可以将一个四连通的部分涂成黑色或白色。相邻格子定义为有公共边的格子。称 $S$ 为四连通，当且仅当 $S$ 中任意两个格子之间都存在一条 $S$ 内路径，满足只在相邻格子间移动。

你需要告诉他，最少需要下笔多少次才能完成画作。

数据范围与提示
$\max (r,c)\le 50$ 。部分分也很难，就不给出了。

思路

话说这个矩阵是连通的，不会真的有人不知道吧 😒

直接猜结论：存在一种最优方案，每次的操作是上一次操作的子集，并且颜色相反。像俄罗斯套娃。

OI结论都要证明的话，跟数竞有什么区别？ 我们来试着证明一下这个结论。用归纳法。

不妨设原来的操作区间依次是 $S_1,S_2,\dots ,S_k$ ，已经满足了这个结论，现在要操作 $T$ 。由于整张画布最初是白色的，规定 $S_0$ 为整个画布，并且其颜色为白色。显然 $T\subseteq S_0$ 。

我们循环执行如下操作，如同迭代：

• 找一个最大的 $x$ 使得 $T\subseteq S_x$ 。如果 $x=k$ 则结论成立，退出迭代。否则有 $T\subseteq S_{x+1}$ 不成立，继续下一步。
• 如果 $T$ 和 $S_x$ 是同色的，那么 $T$ 在 $S_x-S_{x+1}$ 中的部分无用。所以将 $T$ 修改为 $T\cap S_{x+1}$ ，回到第一步。容易发现下一次循环的 $x$ 必定增大。
• 如果 $T$ 和 $S_x$ 是不同色的，那么 $T$ 与 $S_{x+1}$ 同色。分两种情况。
• 1. 若 $T$ 和 $S_{x+1}$ 没有交集，必定存在一个四连通 $M\subseteq S_x$ 满足 $S_{x+1}\subseteq M$ 且 $T\subseteq M$ 。将 $S_{x+1}$ 扩充为 $M$ ，将 $T$ 更改为 $M-T-S_x$ ，也就是将 $S_x$ 和 $T$ 连接起来的部分，然后反转颜色。不难发现 $S$ 序列仍然是满足包含关系的。回到第一步。容易发现下一次的 $x$ 必定增大。
• 2. 若 $T$ 和 $S_{x+1}$ 有交集，令 $S_{x+1}^{\prime }=S_{x+1}\cup T,T^{\prime }=T\cap S_{x+1}$ 即可。回到第一步。容易发现下一次的 $x$ 必定增大。

由于 $x$ 总是在增大，而 $k$ 是不变的，所以迭代将会有出口 $x=k$ ，故结论成立。

有了这个结论，并不好做。但是 时光倒流 就很简单，就像穿棉袄，一圈一圈的增加。最终答案就是 “圈” 的数量。相邻的格子连边，异色则边权为 $1$ ，同色则为 $0$ ，这样就实现了 “圈” 之间的转移为 $1$ ，于是最短路长度即为 “圈” 数 $-1$ 了。于是你枚举一下，哪个点是最后被上色的，其贡献就是它到所有黑点的最短路的最大值。所有贡献取 $\min$ 就是答案。

复杂度 $\mathcal{O}(r^2{c}^2)$ 。不会真的有人不会 $\mathtt{b}\mathtt{f}\mathtt{s}$ 吧？

代码

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
inline int readint(){int a = 0; char c = getchar(), f = 1;for(; c<'0'||c>'9'; c=getchar())if(c == '-') f = -f;for(; '0'<=c&&c<='9'; c=getchar())a = (a<<3)+(a<<1)+(c^48);return a*f;
}const int MaxN = 51;
const int dir[][2] = {{0,1},{1,0},{0,-1},{-1,0}
};
int dis[MaxN][MaxN], n, m;
char maze[MaxN][MaxN+5];
int q[MaxN*MaxN], head, tail;
void addMore(int x,int y){ // 连坐q[++ tail] = x*m+y-1;for(int i=0,tx,ty; i<4; ++i){tx = x+dir[i][0];ty = y+dir[i][1];if(1 <= tx && tx <= n)if(1 <= ty && ty <= m)if(dis[tx][ty] == -1)if(maze[x][y] == maze[tx][ty]){dis[tx][ty] = dis[x][y];addMore(tx,ty);}}
}
int bfs(int x,int y){for(int i=1; i<=n; ++i)for(int j=1; j<=m; ++j)dis[i][j] = -1;head = 0, tail = -1; // emptydis[x][y] = 0; // initaddMore(x,y); // 加入整个点while(head <= tail){int x = q[head]/m, tox;int y = q[head]%m+1;++ head; // pop_frontfor(int i=0,toy; i<4; ++i){tox = x+dir[i][0];toy = y+dir[i][1];if(dis[tox][toy] == -1){dis[tox][toy] = dis[x][y]+1;addMore(tox,toy);}}}int res = 0;for(int i=1; i<=n; ++i)for(int j=1; j<=m; ++j)if(maze[i][j] == '1')res = max(res,dis[i][j]);return res;
}int main(){n = readint(), m = readint();for(int i=1; i<=n; ++i)scanf("%s",maze[i]+1);int ans = n*m; // 最短路 = 圈数-1for(int i=1; i<=n; ++i)for(int j=1; j<=m; ++j)ans = min(ans,bfs(i,j));printf("%d\n",ans+1);return 0;
}