题目

思路

路径只要经过两次拆分和两次合并就是YES

因为长路径必定是由短路径构成的，将最短路径合并让自己处于尽可能左上的位置，这样是最贪心的，也是最优的。

所以找到图中所有的倾斜点对的合并点，再查看右下角矩阵内是否有合并点，以及当前合并点下面和右边是否有合并点，就可以判断当前合并点是否能YES。

两种特殊情况

一个合并点下，第二个合并点的所有可行解

队友敲的代码

#include <bits/stdc++.h>
#define ls o << 1
#define rs o << 1 | 1
using namespace std;
typedef long long ll;
const int maxn = 3000 + 10;
char s[maxn][maxn];
//bool vis[maxn][maxn];
int dp[maxn][maxn];///dp[i][j]  =1表示从(i, j)可以找到下一个交叉路口      = 0 表示不可以
int n, m;
int dfs(int x, int y){if(dp[x][y] >= 0) return dp[x][y];if(x > n || y > m) return 0;int ok = 0;if(s[x + 1][y] == s[x][y + 1] && x + 1 <= n && y + 1 <= m) ok = 1;ok |= dfs(x + 1, y);ok |= dfs(x, y + 1);return dp[x][y] = ok;
}
bool check(int x1, int y1, int x2, int y2){if(x1 > n || x2 > n || y1 > m || y2 > m) return false;return s[x1][y1] == s[x2][y2];
}
int main(){memset(dp, -1, sizeof(dp));scanf("%d%d", &n, &m);for(int i = 1; i <= n; i++){scanf("%s", s[i] + 1);}dfs(1, 1);//printf("%d\n", dp[1][1]);bool ok = false;for(int i = 1; i < n; i++){for(int j = 1; j < m; j++){if(dp[i + 1][j + 1] == 1 && s[i + 1][j] == s[i][j + 1]){ok = true;break;}if(check(i + 1, j, i, j + 1) && check(i + 1, j + 1, i + 2, j)){ok = true;break;}if(check(i + 1, j, i, j + 1) && check(i, j + 2, i + 1, j + 1)){ok = true;break;}}}if(ok){puts("YES");}else{puts("NO");}return 0;
}

自己造的样例

前两个是NO，然后都是YES
/*
2 4
aade
acef

4 4
abcb
debf
gahi
ajkl

3 4
abnq
bcde
hmea

2 3
abc
bcd

7 6
abcdbf
gaibkl
anopqr
stuvwx
yzebcd
eeghij
klmnop

7 6
abcdbf
gaibkl
anopqr
stuvwx
yzabce
efghej
klmnop
*/