收藏
关注
福克斯在玩一款手机解迷游戏，这个游戏叫做”两点”。基础级别的时候是在一个n×m单元上玩的。像这样：
每一个单元有包含一个有色点。我们将用不同的大写字母来表示不同的颜色。
这个游戏的关键是要找出一个包含同一颜色的环。看上图中4个蓝点，形成了一个环。一般的，我们将一个序列 d1,d2,...,dk 看成一个环，当且仅当它符合下列条件时：
1. 这k个点不一样，即当 i≠j时， di 和 dj不同。
2. k至少是4。
3. 所有的点是同一种颜色。
4. 对于所有的 1≤i≤k-1: di 和 di+1 是相邻的。还有 dk 和 d1 也应该相邻。单元 x 和单元 y 是相邻的当且仅当他们有公共边。
当给出一幅格点时，请确定里面是否有环。
Input
单组测试数据。 第一行包含两个整数n和m (2≤n,m≤50):板子的行和列。 接下来n行，每行包含一个有m个字母的串，表示当前行每一个点的颜色。每一个字母都是大写字母。
Output
如果有环输出Yes，否则输出No。
Input示例
3 4 AAAA ABCA AAAA 3 4 AAAA ABCA AADA
Output示例
Yes No
这道题居然还想了很久，多明显的深搜，回到原地就OK了。
代码：
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#pragma warning(disable:4996)
using namespace std;
#define down 0
#define up 1
#define left 2
#define right 3
int s, e;
int fin;
int n, m;
char val[52][52];
int vis[52][52];
void dfs(int x, int y, int flag,char value)
{
if (fin == 1)
return;
if (x == s&&y == e&&vis[x][y])
{
fin = 1;
return;
}
if (flag == down)
{
if (value == val[x + 1][y]&& !vis[x + 1][y])
{
vis[x + 1][y] = 1;
dfs(x + 1, y, down, value);
}
if (value == val[x][y + 1] && !vis[x][y + 1])
{
vis[x][y + 1] = 1;
dfs(x, y + 1, right, value);
}
if (value == val[x][y - 1]&& !vis[x][y - 1])
{
vis[x][y - 1] = 1;
dfs(x, y - 1, left, value);
}
}
else if (flag == up)
{
if (value == val[x - 1][y]&&!vis[x-1][y])
{
vis[x - 1][y] = 1;
dfs(x - 1, y, up, value);
}
if (value == val[x][y - 1] && !vis[x][y - 1])
{
vis[x][y - 1] = 1;
dfs(x, y - 1, left, value);
}
if (value == val[x][y + 1] && !vis[x][y + 1])
{
vis[x][y + 1] = 1;
dfs(x, y + 1, right, value);
}
}
else if (flag == right)
{
if (value == val[x - 1][y] && !vis[x - 1][y])
{
vis[x - 1][y] = 1;
dfs(x - 1, y, up, value);
}
if (value == val[x][y + 1] && !vis[x][y + 1])
{
vis[x][y + 1] = 1;
dfs(x, y + 1, right, value);
}
if (value == val[x + 1][y] && !vis[x + 1][y])
{
vis[x + 1][y] = 1;
dfs(x + 1, y, down, value);
}
}
else if (flag == left)
{
if (value == val[x][y - 1] && !vis[x][y - 1])
{
vis[x][y - 1] = 1;
dfs(x, y - 1, left, value);
}
if (value == val[x - 1][y] && !vis[x - 1][y])
{
vis[x - 1][y] = 1;
dfs(x - 1, y, up, value);
}
if (value == val[x + 1][y] && !vis[x + 1][y])
{
vis[x + 1][y] = 1;
dfs(x + 1, y, down, value);
}
}
}
int main()
{
//freopen("i.txt","r",stdin);
//+freopen("o.txt","w",stdout);
int i, j, k;
cin >> n >> m;
for (i = 1; i <= n; i++)
cin >> val[i] + 1;
for (i = 1; i <= n; i++)
{
for (j = 1; j <= m; j++)
{
fin = 0;
s = i;
e = j;
memset(vis, 0, sizeof(vis));
dfs(i, j, down, val[i][j]);
if (fin == 1)
{
cout << "Yes" << endl;
return 0;
}
}
}
cout << "No" << endl;
//system("pause");
return 0;
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
