P10270 好奇心宝贝

贪心

题目大意

给定一个 $n\times m$ 的矩阵，要选择两条 $(1,1)$ 到 $(n,m)$ 的路径，要求每次都只能往下面或者右边一个格子走。现在你需要求出这两条路径的最小前缀。

思路

首先，题目告诉了我们每一个格子只能往下面或者右边走，因此路径的长度一定为 $n+m-1$，也可以将矩阵斜着切分为 $n+m-1$ 个格子。既然是最大前缀最小，那么只需要有斜排有不一样的元素就可以了，这样子我们就可以专门走不一样的格子，使得答案尽量小。

至于如何存储每一斜排的所有元素，可以使用 STL 当中的 unordered_set 实现。注意需要特殊判断矩阵当中全是同一个字符的情况，其实循环到 $n+m$ 就行了。时间复杂度 $\mathcal{O}(n\times m)$。

代码

#include <iostream>
#include <unordered_set>
 
using namespace std;
 
const int kMaxN = 2e3 + 5;
 
int n, m;
char c;
unordered_set<char> s[kMaxN * kMaxN];
 
int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> c, s[i + j - 1].insert(c);
    }
  }
  for (int i = 1; i <= n + m; i++) {
    if (s[i].size() != 1) {
      return cout << i - 1, 0;
    }
  }
  return 0;
}