题目描述

有一款名为“Two Dots”的移动益智游戏。有一个大小为 $n \times m$的方格，每格都是某种颜色的点（将使用不同的大写字母表示不同的颜色）。

这个游戏的关键是找到一个包含相同颜色点的循环。例如上图中的 $4$ 个蓝色圆点就是一个环。当且仅当满足以下条件时，一系列点 $d_1 ，d_2 ，\dots ，d_k$ 为一个环：

(1) 这些 $k$ 点是不同的：如果 $i≠j$ ，则 $d_i$ 与 $d_j$ 不同。

(2) $k$ 至少为 $4$ 。

(3) 对于所有的点都具有同一种颜色。

(4) 对于所有 $1 \le i \le k-1$：$d_i$和$d_{i+1}$是相邻的，另外，$d_k$ 和 $d_1$ 也是相邻。 如果 $x$ 和 $y$ 共享边，则称它们相邻。

请确定该所给的 $n \tmes m$ 方格中是否存在环。

输入

第一行一个数 $T$ （$2 \le T \le 10$） ，表示有 $T$ 组数据。以下每组数据：

第一行两个数为 $N, M$ （$2 \le N, M \le 50$），表示该表格的行数和列数。

以下 $N$ 行每行 $M$ 个大写字母表示方格中的颜色。

输出

$T$ 行，对应每组数据若能满足要求，则输出“Yes”，否则输出“No”。

Input

5
3 4
AAAA
ABCA
AAAA
3 4
AAAA
ABCA
AADA
4 4
YYYR
BYBY
BBBY
BBBY
7 6
AAAAAB
ABBBAB
ABAAAB
ABABBB
ABAAAB
ABBBAB
AAAAAB
2 13
ABCDEFGHIJKLM
NOPQRSTUVWXYZ

Output

Yes
No
Yes
Yes
No

CODE

#include<bits/stdc++.h>
using namespace std;
const int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};
int t,n,m,d[509][509];//组数、行数、列数与存放搜索序
char g[509][509];//记录图
bool flag;//标记是否搜索到环
string s;//临时记录一行的数据
void dfs(int x,int y,int t){
    d[x][y]=t;//记录搜索序
    for (int i=0;i<4;i++){
    	  if (flag) return;//如果已经搜索到了则无需再找
        int x1=x+dx[i],y1=y+dy[i];
        if (g[x1][y1]!=g[x][y]) continue;//若目标点的颜色与当前点不同则跳过
        if (d[x1][y1]){
            if (t-d[x1][y1]>=4) flag=1;
            continue;
        }//标记已搜索到环并跳过下次搜索
        dfs(x1,y1,t+1);
    }
}
int main(){
    cin>>t;
    while (t--){
        cin>>n>>m;
        flag=0;
        memset(g,'0',sizeof(g));
        memset(d,0,sizeof(d));
        for (int i=1;i<=n;i++){
            cin>>s;
            for (int j=0;j<m;j++) g[i][j+1]=s[j];
        }
        for (int i=1;i<=n;i++){
            for (int j=1;j<=m;j++) dfs(i,j,1);
        }
        if (!flag) cout<<"No"<<endl;
        else cout<<"Yes"<<endl;
    }
    return 0;
}

感谢各位大神的帮助