深度优先搜索练习之神奇的矩环-蒲公英云

深度优先搜索练习之神奇的矩环

think:
1感觉自己用的不是深度优先搜索啊，——话落即发现如何判错自己的代码，人果然还是否定自己比较容易..无语啊

sdut原题链接

深度优先搜索练习之神奇的矩环
Time Limit: 1000MS Memory Limit: 65536KB

Problem Description
小鑫的女朋友被魔王抢走了！
魔王留给小鑫一张n*m大的表，上面有各种各样的颜色，用A-Z这26个字母来表示。魔王留给他一个任务，如果小鑫可以在这张表中找出任意一个长度大于1的环，并且这个环的颜色是相同的，魔王就把小鑫的女朋友还给他。为了从魔王手中夺回他的女朋友，小鑫请你帮忙，你能帮帮他吗？

Input
多组输入。
每组的第一行有两个整数n,m。代表表的大小。
接下来是由A-Z的一些字母所构成的n行m列的表。
1<=n,m<=200

Output
如果可以救回他的女朋友，输出Yes，否则输出No

Example Input
4 7
ABCBBAA
BCBCBCB
AABBCCA
ACCCBBB
10 3
AAC
ABB
BBA
AAC
CBC
CCA
CBB
CCA
CCB
BAA

Example Output
No
Yes

Hint

Author

以下为accpted代码——感觉后台数据和自己挺亲的
数据
5 5
AAAAA
ABBBA
AAAAA
CCCCC
AAAAA
即可判错以下代码

#include <stdio.h>
#include <string.h>
int main()
{
    int n, m, i, j;
    char s[204][204];
    while(scanf("%d %d", &n, &m) != EOF)
    {
        int flag = 0;
        for(i = 0; i < n; i++)
        {
            scanf("%s", s[i]);
        }
        for(i = 0; i < n-1; i++)
        {
            for(j = 0; j < m-1; j++)
            {
                if(s[i][j] == s[i][j+1])
                {
                    if(s[i][j] == s[i+1][j])
                    {
                        if(s[i][j] == s[i+1][j+1])
                        {
                            flag = 1;
                            break;
                        }
                    }
                }
            }
            if(j != m-1)
                break;
        }
        if(flag)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}
/***************************************************
User name: 
Result: Accepted
Take time: 0ms
Take Memory: 120KB
Submit time: 2017-02-16 20:53:44
****************************************************/

以下为accepted建议参考代码

#include <stdio.h>
#include <string.h>
char map[200][200];
int v[200][200], flag;
void dfs(int x, int y, int x1, int y1, int n, int m)
{
    v[x][y] = 1;
    if(flag == 1)
    {
        return;
    }
    if(y-1 >= 0 && map[x][y] == map[x][y-1])
    {
        if(v[x][y-1] == 1 && (x != x1 || y-1 != y1))
        {
            flag = 1;
        }
        else if(v[x][y-1] == 0)
        {
            dfs(x, y-1, x, y, n, m);
        }
    }
    if(x-1 >= 0 && map[x][y] == map[x-1][y])
    {
        if(v[x-1][y] == 1 && (x-1 != x1 || y != y1))
        {
            flag = 1;
        }
        else if(v[x-1][y] == 0)
        {
            dfs(x-1, y, x, y, n, m);
        }
    }
    if(y+1 < m && map[x][y] == map[x][y+1])
    {
        if(v[x][y+1] == 1 && (x != x1 || y+1 != y1))
        {
            flag = 1;
        }
        else if(v[x][y+1] == 0)
        {
            dfs(x, y+1, x, y, n, m);
        }
    }
    if(x+1 < n && map[x][y] == map[x+1][y])
    {
        if(v[x+1][y] == 1 && (x+1 != x1 || y != y1))
        {
            flag = 1;
        }
        else if(v[x+1][y] == 0)
        {
            dfs(x+1, y, x, y, n, m);
        }
    }
}
int main()
{
    int n, m, i, j;
    while(scanf("%d %d", &n, &m) != EOF)
    {
        flag = 0;
        memset(v, 0, sizeof(v));
        for(i = 0; i < n; i++)
        {
            scanf("%s", map[i]);
        }
        for(i = 0; i < n; i++)
        {
            for(j = 0; j < m; j++)
            {
                if(v[i][j] == 0)
                {
                    dfs(i, j, i, j, n, m);
                }
                if(flag == 1)
                {
                    break;
                }
            }
            if(j != m)
            {
                break;
            }
        }
        if(flag)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}
/***************************************************
User name: 
Result: Accepted
Take time: 4ms
Take Memory: 280KB
Submit time: 2017-02-16 21:40:33
****************************************************/