自动搬运

查看原文

来自洛谷，原作者为

	Pursuewind 等风来，不如追风去 || 初一 OIER || qq:2829259510

搬运于2025-08-24 22:56:22，当前版本为作者最后更新于2024-03-24 21:37:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一开始我以为是 BFS（虽然好像可以用 BFS 做），但是发现我把这道题想复杂了。

思路：

写在前面：设一个点 $(i,j)$ 到点 $(1,1)$ 的距离是 $i+j-1$，即从 $(1,1)$ 出发到该点连成字符串的长度。

这道题解题的关键是从点 $(1,1)$ 走到点 $(i,j)$，不管怎样走，连成的字符串长度都是 $i+j-1$。

枚举答案 $ans$，从 $1$ 到 $n+m-1$，每一次找到一些点，使得这些点与 $(1,1)$ 的距离都为 $ans$。此时，若这些点上的字符有不相同，则答案为 $ans-1$，直接输出即可。

下面来证明一下：

如果有两个与 $(1,1)$ 距离相同的点，记为 $(x_1,y_1)$ 和 $(x_2,y_2)$，那么它们连成的字符串各是（$c$ 表示输入矩阵）：

上面的 $+$ 表示连接字符。

此时由于 $c_{x_1,y_1} \not = c_{x_2,y_2}$，而可以得知两条路径前面的 $ans-1$ 个字符都相等，所以答案为 $ans-1$。

为什么此时两条路径前面的 $ans-1$ 个字符都相等呢？因为如果前面的 $ans-1$ 个字符不相等，那么答案就会被更小的 $ans$ 代替。

于是就可以得到代码了，复杂度 $O(nm \log n)$（我赛时太着急了，用 set 维护了互不相同的字符，其实不用这样，可以将复杂度优化至 $O(nm)$ 的）：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e3 + 5;
char c[N][N];
set <char> s;
signed main(){
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i ++){
		for (int j = 1; j <= m; j ++){
			cin >> c[i][j];
		}
	}
	for (int d = 1; d < n + m; d ++){
		s.clear();
		for (int x = 1; x <= n; x ++){
			int y = d - x + 1;
          //此时(x,y)和(1,1)的距离是 d
			if (y > 0 && y <= m) s.insert(c[x][y]);
		}//x+y-1=d
		if (s.size() != 1){
			cout << d - 1 << "\n";
			return 0;
		}
	}
	cout << n + m - 1 << "\n"; //这里要注意，有可能整个矩阵的字符都相等，此时的答案为 n+m-1
	return 0;
}