有一个 n×m 的方格矩阵,每个方格都有一种颜色。

颜色最多不超过 26 种,我们将使用不同的大写英文字母来表示不同的颜色。

你的任务是在矩阵中找到一个规模不小于 4 的同色环。

也就是说,请你在矩阵中找到 k 个不同的方格,要求它们能够同时满足:

  • k ≥ 4
  • k 个方格的颜色相同。
  • 将这 k 个方格按某种顺序编号为 1∼k 后,能够满足方格 1 与方格 2 相邻、方格 2 与方格 3 相邻、…、方格 k-1 与方格 k 相邻、方格 k 与方格 1 相邻。如果两个方格存在公共边,则称两个方格相邻。

请你判断,在给定矩阵中是否存在满足条件的同色环。

输入格式:

第一行包含两个整数 n,m

接下来 n 行,每行包含一个长度为 m 的由大写字母构成的字符串,用来表示矩阵中每个方格的颜色。

输出格式:

如果给定矩阵中存在满足条件的同色环,则输出 Yes,否则输出 No

数据范围:

前 6 个测试点满足 2 ≤ n,m ≤ 10。 所有测试点满足 2 ≤ n,m ≤ 50。

输入样例1:

3 4
DDDD
DBCD
DDDD

输出样例1:

Yes

输入样例2:

3 4
EEEE
EBCE
EEDE

输出样例2:

No

输入样例3:

4 4
AAAB
CACA
CCCA
CCCA

输出样例3:

Yes

输入样例4:

7 6
XXXXXY
XYYYXY
XYXXXY
XYXYYY
XYXXXY
XYYYXY
XXXXXY

输出样例4:

Yes

代码实现

#include <iostream>
#include <bitset>
#define x first
#define y second
using namespace std;
using PII = pair <int,int>;
const int N = 55;

int n, m;
char g[N][N];
bitset <N> st[N];
PII dir[4] = {{-1,0},{0,1},{1,0},{0,-1}};
bool dfs(int x, int y, int from) {
    st[x][y] = 1;
    for (int k = 0; k < 4; ++k) {
        if ((k ^ 2) == from) continue;
        int a = x + dir[k].x, b = y + dir[k].y;
        if (a < 0 || b < 0 || a >= n || b >= m || g[a][b] != g[x][y]) continue;
        if (st[a][b]) return 1;   
        if(dfs(a, b, k)) return 1;
    }
    return 0;
}
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            cin >> g[i][j];
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (!st[i][j]) {
                if(dfs(i, j, -1)) {
                    cout << "Yes";
                    return 0;
                }
            }
    cout << "No";
    return 0;
} 
分类: DFS

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status