51Nod - 1416 搜索环

题意：

福克斯在玩一款手机解迷游戏，这个游戏叫做”两点”。基础级别的时候是在一个n×m单元上玩的。像这样：

每一个单元有包含一个有色点。我们将用不同的大写字母来表示不同的颜色。

这个游戏的关键是要找出一个包含同一颜色的环。看上图中4个蓝点，形成了一个环。一般的，我们将一个序列 d₁,d₂,...,d_k 看成一个环，当且仅当它符合下列条件时：

1.    这k个点不一样，即当 i≠j时， d_i 和 d_j不同。

2.    k至少是4。

3.    所有的点是同一种颜色。

4.    对于所有的 1≤i≤k-1: d_i 和 d_i+1 是相邻的。还有 d_k 和 d₁ 也应该相邻。单元 x 和单元 y 是相邻的当且仅当他们有公共边。

当给出一幅格点时，请确定里面是否有环。

单组测试数据。第一行包含两个整数n和m (2≤n,m≤50):板子的行和列。接下来n行，每行包含一个有m个字母的串，表示当前行每一个点的颜色。每一个字母都是大写字母。Output
如果有环输出Yes，否则输出No。Input示例
3 4AAAAABCAAAAA3 4AAAAABCAAADAOutput示例
YesNo
思路：
简单的搜索环，将相同颜色且互相可以到达的点都连上边然后判断是否存在环就行了，按照这样的建图方式，如果有环一定不小于4，所以不需要判断环的大小。
代码：
#include <bits/stdc++.h>using namespace std;const int MAXN = 55;char str[MAXN][MAXN];vector <int> G[MAXN * MAXN];bool vis[MAXN * MAXN];bool dfs(int u, int PRe) {    vis[u] = true;    int cnt = G[u].size();    for (int i = 0; i < cnt; i++) {        int v = G[u][i];        if (v == pre) continue;        if (vis[v] || dfs(v, u)) return true;    }    return false;}const int dx[] = {-1, 1, 0, 0};const int dy[] = {0, 0, -1, 1};int main() {    int n, m;    scanf("%d%d", &n, &m);    for (int i = 0; i < n; i++) {        scanf("%s", str[i]);    }    for (int x = 0; x < n; x++) {        for (int y = 0; y < m; y++) {            int u = x * m + y;            for (int k = 0; k < 4; k++) {                int nx = x + dx[k], ny = y + dy[k];                if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;                if (str[nx][ny] != str[x][y]) continue;                int v = nx * m + ny;                G[u].push_back(v);            }        }    }    for (int i = 0; i < n; i++) {        for (int j = 0; j < m; j++) {            int u = i * m + j;            if (vis[u]) continue;            if (dfs(u, -1)) {                puts("Yes");                return 0;            }        }    }    puts("No");    return 0;}