两点

àì夳堔傛蜴生んèń 2022-06-11 00:37 84阅读 0赞

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

![d41d8cd98f00b204e9800998ecf8427e_v_1500951816][]   
![383289b5b551070ff82a786ae4eaee25_v_1500951816][]

![d41d8cd98f00b204e9800998ecf8427e_v_1500951816][]

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

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

1.    这k个点不一样，即当 i≠j时， *di* 和 *dj*不同。

2.    k至少是4。

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

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

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

Input

单组测试数据。   
第一行包含两个整数n和m (2≤n,m≤50):板子的行和列。   
接下来n行，每行包含一个有m个字母的串，表示当前行每一个点的颜色。每一个字母都是大写字母。

Output

如果有环输出Yes，否则输出No。

Sample Input

3 4
    AAAA
    ABCA
    AAAA
    3 4
    AAAA
    ABCA
    AADA

Sample Output

Yes
    No

#include<cstdio>
    #include<vector>
    #include<cstring>
    #include<algorithm>
    using namespace std;
    const int inf=0x3f3f3f3f;
    int n,m;
    int vis[2510];
    char map1[51][51];//一开始定义为int去了，找了老半天，真想骂人
    vector<int> V[2510];
    int dx[]={-1,1,0,0};
    int dy[]={0,0,-1,1};
    void build(int x,int a,int b)
    {
        for(int i=0;i<4;i++)
        {
            int xx=a+dx[i];
            int yy=b+dy[i];
    //        printf("a=%d b=%d",a,b);
    //        printf("xx=%d yy=%d\n",xx,yy);
            if(xx>=0&&xx<n&&yy>=0&&yy<m&&map1[xx][yy]==map1[a][b])
            {
                int e=xx*m+yy;
                //printf("e=%d x=%d\n",e,x);
                V[x].push_back(e);
            }
        }
    }
    int dfs(int x1,int x2)
    {
        vis[x1]=1;
        int len=V[x1].size();
        for(int i=0;i<len;i++)
        {
            int aa=V[x1][i];
            if(aa==x2) continue;
            //printf("%d ",aa);
            if(vis[aa]||dfs(aa,x1))
                return 1;
        }
        return 0;
    }
    int main()
    {
        while(~scanf("%d %d",&n,&m))
        {
            for(int i=0;i<2510;i++)
            V[i].clear();
            for(int i=0;i<n;i++)
                scanf("%s",map1[i]);
            memset(vis,0,sizeof(vis));
            for(int i=0;i<n;i++)
            {
                for(int j=0;j<m;j++)
                {
                    int s=i*m+j;
                    build(s,i,j);
                }
            }
            int ok=0;
            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,inf))
                    {
                        printf("Yes\n");
                        ok=1;
                        break;
                    }
                }
                if(ok)
                    break;
            }
            if(!ok)
                printf("No\n");
        }
        return 0;
    }

[d41d8cd98f00b204e9800998ecf8427e_v_1500951816]: https://odzkskevi.qnssl.com/d41d8cd98f00b204e9800998ecf8427e?v=1500951816
[383289b5b551070ff82a786ae4eaee25_v_1500951816]: https://odzkskevi.qnssl.com/383289b5b551070ff82a786ae4eaee25?v=1500951816