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

￡神魔★判官ぃ 2022-07-12 07:49 91阅读 0赞

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

[sdut原题链接][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
    ****************************************************/

[sdut]: http://acm.sdut.edu.cn/onlinejudge2/index.php/Home/Contest/contestproblem/cid/2012/pid/3469