ACM模版

描述


题解

深度优先搜索，这里需要强调的是，不要归置状态，只要访问过就标记为1，另外需要设置一个tag标签，标记上一步，防止下一步与上一步重合。当访问的下一步所访问的点已经被访问过，说明形成了环。

代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int MAXMN = 55;

int n, m;
char map[MAXMN][MAXMN];
int flag[MAXMN][MAXMN]; // 标记访问状态
bool ans = false;

void solve(int x, int y, int tag)
{
    if (x > n || x < 1)
    {
        return ;
    }
    else if (y > m || y < 1)
    {
        return ;
    }
    flag[x][y] = 1;
    // 一号路径
    if (map[x][y] == map[x + 1][y] && tag != 2)
    {
        if (flag[x + 1][y])
        {
            ans = true;
            return ;
        }
        solve(x + 1, y, 1);
    }
    // 二号路径
    if (map[x][y] == map[x - 1][y] && tag != 1)
    {
        if (flag[x - 1][y])
        {
            ans = true;
            return ;
        }
        solve(x - 1, y, 2);
    }
    // 三号路径
    if (map[x][y] == map[x][y + 1] && tag != 4)
    {
        if (flag[x][y + 1])
        {
            ans = true;
            return ;
        }
        solve(x, y + 1, 3);
    }
    // 四号路径
    if (map[x][y] == map[x][y - 1] && tag != 3)
    {
        if (flag[x][y - 1])
        {
            ans = true;
            return ;
        }
        solve(x, y - 1, 4);
    }
    return ;
}

int main(int argc, const char * argv[])
{
    while (cin >> n >> m)
    {
        memset(flag, 0, sizeof(flag));

        for (int i = 1; i <= n; i++)
        {
            scanf("%s", map[i] + 1);
        }
        for (int i = 1; i <= n; i++)
        {
            if (ans)
            {
                break;
            }
            for (int j = 1; j <= m; j++)
            {
                if (ans)
                {
                    break;
                }
                if (!flag[i][j])
                {
                    solve(i, j, 0);
                }
            }
        }
        if (ans)
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }

    return 0;
}