问题 J: 棋盘行走
时间限制: 1 Sec 内存限制: 128 MB
[命题人: http://icpc.ldu.edu.cn/userinfo.php?user=admin ]
题目描述
小 Biu 在玩一个棋盘游戏, 这个游戏给出一个 n*m 的棋盘, 并且每个点上有一个棋子, 棋子的颜色
用一个大写字母表示.
小 Biu 获得游戏胜利的条件是:
1. 选择一个棋子作为起点.
2. 每次只能走上下左右四个方格, 并且下一步方格的颜色要与当前格颜色相同
3. 每个块只能经过一次, 要经过不少于 4 个不同的格子而且最终要走回起点.
问小 Biu 是否可以赢得游戏的胜利
输入
第一行包含两个整数 n 和 m (2≤n,m≤50): 棋盘的行和列.
接下来 n 行, 每行包含一个有 m 个字母的串, 表示当前行每一个点的颜色. 每一个字母都是大写字母.
输出
如果小 Biu 可以获得胜利输出 Yes, 否则输出 No.
样例输入 Copy
3 4 AAAA ABCA AAAA
样例输出 Copy
Yes
提示
1. 样例解释
样例中所有的'A'形成一个环.
2. 数据范围
对于 20% 的数据, n *m<=10;
对于 65% 的数据, n *m<=100;
对于 100% 的数据, n *m<=2500;
AC 代码 1:
- #pragma GCC optimize(2)
- #include<bits/stdc++.h>
- using namespace std;
- inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
- typedef long long ll;
- char a[52][52];
- int n,m;
- int flag=0;
- int vis[4][2] = {
- { 0, 1 },
- { 1, 0 },
- { 0, -1 },
- { -1, 0 } };
- int c[52][52]={0};
- int d[52][52]={0};
- void dfs(char ch,int x,int y,int t){
- if(flag){
- return ;
- }
- if(d[x][y]&&t>3){
- flag=1;
- return ;
- }
- for(int k=0;k<4;k++){
- int xx=x+vis[k][0];
- int yy=y+vis[k][1];
- if ( xx>=n || xx<0 || yy>=m || yy<0 || c[xx][yy] || ch!=a[xx][yy] )
- continue;
- c[xx][yy]=1;
- dfs(ch,xx,yy,t+1);
- c[xx][yy]=0;
- }
- }
- int main()
- {
- memset(c,0,sizeof(c));
- memset(d,0,sizeof(d));
- cin>>n>>m;
- for(int k=0;k<n;k++){
- cin>>a[k];
- }
- for(int i=0;i<n;i++){
- for(int j=0;j<m;j++){
- d[i][j]=1;
- dfs(a[i][j],i,j,0);
- if(flag==1){
- break;
- }
- d[i][j]=0;
- }
- if(flag){
- break;
- }
- }
- if(flag){
- printf("Yes\n");
- }
- else{
- printf("No\n");
- }
- return 0;
- }
AC 代码 2:
- #pragma GCC optimize(2)
- #include<bits/stdc++.h>
- using namespace std;
- inline int read() {int x=0,f=1;char c=getchar();while(c!='-'&&(c<'0'||c>'9'))c=getchar();if(c=='-')f=-1,c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return f*x;}
- typedef long long ll;
- char a[52][52];
- int n,m;
- int flag=0;
- int vis[4][2] = {
- { 0, 1 },
- { 1, 0 },
- { 0, -1 },
- { -1, 0 } };
- int c[52][52]={0};
- int d[52][52]={0};
- void dfs(char ch,int x,int y,int t){
- if(flag){
- return ;
- }
- for(int k=0;k<4;k++){
- int xx=x+vis[k][0];
- int yy=y+vis[k][1];
- if(d[xx][yy]&&t>3){
- flag=1;
- return ;
- }
- if ( xx>=n || xx<0 || yy>=m || yy<0 || c[xx][yy] || ch!=a[xx][yy] )
- continue;
- c[xx][yy]=1;
- dfs(ch,xx,yy,t+1);
- c[xx][yy]=0;
- }
- }
- int main()
- {
- memset(c,0,sizeof(c));
- memset(d,0,sizeof(d));
- cin>>n>>m;
- for(int k=0;k<n;k++){
- cin>>a[k];
- }
- for(int i=0;i<n;i++){
- for(int j=0;j<m;j++){
- d[i][j]=1;
- c[i][j]=1;
- dfs(a[i][j],i,j,1);
- if(flag==1){
- break;
- }
- d[i][j]=0;
- c[i][j]=1;
- }
- if(flag){
- break;
- }
- }
- if(flag){
- printf("Yes\n");
- }
- else{
- printf("No\n");
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3377050.html