题解：P10270 好奇心宝贝

zibenlun · 2024-03-25 09:01:00 · 题解

思路

首先我们将整个矩形按照与起点的距离分成不同的层，我们可以发现只要这一层有两个以上的不同的字母，那么我们在走到这一层的时候一定可以使这一位不同，所以我们就只需要找到最小的有多于一种字母的层数就行了。时间复杂度 O(n^2)。

代码

#include<bits/stdc++.h>
#define ll long long
#define int long long
#define int_128 __int128
#define lowbit(x) (x&(-x))
using namespace std;
set<int> s[4005];
int n,m;
char a[2005][2005];
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            s[i-1+j-1+1].insert(a[i][j]);
        }
    }
    for(int i=1;i<=n+m-1;i++){
        if(s[i].size()>1){
            cout<<i-1;
            return 0;
        }
    }
    cout<<n+m-1;
    return 0;
}