[原创]华中农业大学第五届程序设计大赛 J Color Circle

2017-05-26 22:41:01 Tabris_ 阅读数：317

博客爬取于2020-06-14 22:40:28
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/72774870

题目连接：http://acm.hzau.edu.cn/problem.php?id=1208
——————————————————————
1208: Color Circle
Time Limit: 1 Sec Memory Limit: 1280 MB
Submit: 344 Solved: 104
[Submit][Status][Web Board]
Description
There are colorful flowers in the parterre in front of the door of college and form many beautiful patterns. Now, you want to find a circle consist of flowers with same color. What should be done ?

Assuming the flowers arranged as matrix in parterre, indicated by a N*M matrix. Every point in the matrix indicates the color of a flower. We use the same uppercase letter to represent the same kind of color. We think a sequence of points d1, d2, … dk makes up a circle while:

  1. Every point is different.

  2. k >= 4

  3. All points belong to the same color.

  4. For 1 <= i <= k-1, di is adjacent to di+1 and dk is adjacent to d1. ( Point x is adjacent to Point y while they have the common edge).

    N, M <= 50. Judge if there is a circle in the given matrix.

Input
There are multiply test cases.

In each case, the first line are two integers n and m, the 2nd ~ n+1th lines is the given n*m matrix. Input m characters in per line.

Output
Output your answer as “Yes” or ”No” in one line for each case.

Sample Input
3 3
AAA
ABA
AAA
Sample Output
Yes

————————————————————————————
题目大意：

问你能不能找到一个由一种颜色构成的圈
有求，
1.至少有4个点
2.所有点首尾相接构成一个圈
3.颜色相同
4.点是不同的

解题思路：

由于图很小，所以暴力搜就好了，

附本题代码
——————————————————————————

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
# include <bits/stdc++.h>
typedef long long int LL;
using namespace std;

const int N   = 2e5+7;
//const int INF = (~(1<<31));

int read(){
    int x=0,f=1;char ch = getchar();
    while(ch<'0'||ch>'9') ch = getchar();
    while('0'<=ch&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch = getchar();}
    return x;
}
/*******************************************/

char a[111][111];
int vis[111][111];
int n,m;
bool flag,flag2;

int fx[]={0,0,1,-1};
int fy[]={1,-1,0,0};

void dfs(int x,int y,int dep){
    if(flag) return ;
    int xx,yy;
    for(int i=0;i<4;i++){
        xx=x+fx[i];
        yy=y+fy[i];
        if(xx<1||xx>n||yy<1||yy>m)  continue;
        if(a[xx][yy]!=a[x][y]) continue;

        if(vis[xx][yy]&&dep-vis[xx][yy]+1>=4) {flag = true;return ;}
        else if(!vis[xx][yy]) {
            vis[xx][yy]=dep;
            dfs(xx,yy,dep+1);
            vis[xx][yy]=0;
        }
    }
}

int main(){
    while(~scanf("%d%d",&n,&m)){memset(vis,0,sizeof(vis));
        for(int i=1;i<=n;i++)     scanf("%s",a[i]+1);
        flag = flag2 = false;
        for(int i=1;i<=n&&!flag2;i++)
            for(int j=1;j<=m&&!flag2;j++){
                dfs(i,j,1);
                if(flag) flag2=true;
            }

        if(flag2) puts("Yes");
        else      puts("No");
    }
    return 0;
}