题目链接：http://codeforces.com/problemset/problem/510/B
题目意思：给出 n 行 m 列只有大写字母组成的字符串。问具有相同字母的能否组成一个环。
很容易知道要用到深搜。暴力搜索～～～
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std; const int maxn = + ;
char g[maxn][maxn];
bool vis[maxn][maxn]; int dx[] = {, , , -};
int dy[] = {, , -, }; int n, m; bool dfs(int x, int y, int px, int py, char c)
{
vis[x][y] = ;
for (int i = ; i < ; i++) {
int tx = x + dx[i];
int ty = y + dy[i];
if (tx == px && ty == py) // 和上一次走过的点冲突
continue;
if (tx >= && tx < n && ty >= && ty < m && g[tx][ty] == c) {
if (vis[tx][ty]) // 形成环
return ;
if (dfs(tx, ty, x, y, c))
return ;
}
}
return ;
} int main()
{
while (scanf("%d%d", &n, &m) != EOF) {
for (int i = ; i < n; i++)
scanf("%s", g[i]);
memset(vis, , sizeof(vis)); bool flag = false;
for (int i = ; i < n && !flag; i++) {
for (int j = ; j < m && !flag; j++) {
if (!vis[i][j]) {
if (dfs(i, j, -, -, g[i][j])) {
flag = true;
break;
}
}
}
}
printf("%s\n", flag ? "Yes" : "No");
}
return ;
}
cgy4ever 的代码：
#include <bits/stdc++.h>
using namespace std; int n, m;
string board[];
bool visited[][];
bool findCycle = false;
int dx[] = {, -, , };
int dy[] = {, , , -}; void dfs(int x, int y, int fromX, int fromY, char needColor)
{
if(x < || x >= n || y < || y >= m) return;
if(board[x][y] != needColor) return;
if(visited[x][y])
{
findCycle = true;
return;
}
visited[x][y] = true;
for(int f = ; f < ; f++)
{
int nextX = x + dx[f];
int nextY = y + dy[f];
if(nextX == fromX && nextY == fromY) continue;
dfs(nextX, nextY, x, y, needColor);
}
} int MAIN()
{
cin >> n >> m;
for(int i = ; i < n; i++)
cin >> board[i];
memset(visited, false, sizeof(visited));
for(int i = ; i < n; i++)
for(int j = ; j < m; j++)
if(!visited[i][j])
dfs(i, j, -, -, board[i][j]);
cout << (findCycle ? "Yes" : "No") << endl;
return ;
} int main()
{
#ifdef LOCAL_TEST
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
ios :: sync_with_stdio(false);
cout << fixed << setprecision();
return MAIN();
}