本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 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;
}