Solution - P10270

· · 题解

一开始我以为是 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 表示输入矩阵）：

s_1=c_{1,1}+\dots+c_{x_1,y_1} s_2=c_{1,1}+\dots+c_{x_2,y_2}

上面的 + 表示连接字符。

此时由于 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;
}