Fox And Two Dots
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
Fox Ciel is playing a mobile puzzle game called "Two Dots". The basic levels are played on a board of size n × m cells, like this:
Each cell contains a dot that has some color. We will use different uppercase Latin characters to express different colors.
The key of this game is to find a cycle that contain dots of same color. Consider 4 blue dots on the picture forming a circle as an example. Formally, we call a sequence of dots d1, d2, ..., dk a cycle if and only if it meets the following condition:
- These k dots are different: if i ≠ j then di is different from dj.
- k is at least 4.
- All dots belong to the same color.
- For all 1 ≤ i ≤ k - 1: di and di + 1 are adjacent. Also, dk and d1 should also be adjacent. Cells x and y are called adjacent if they share an edge.
Determine if there exists a cycle on the field.
Input
The first line contains two integers n and m (2 ≤ n, m ≤ 50): the number of rows and columns of the board.
Then n lines follow, each line contains a string consisting of m characters, expressing colors of dots in each line. Each character is an uppercase Latin letter.
Output
Output "Yes" if there exists a cycle, and "No" otherwise.
Sample test(s)
input
3 4
AAAA
ABCA
AAAA
output
Yes
input
3 4
AAAA
ABCA
AADA
output
No
input
4 4
YYYR
BYBY
BBBY
BBBY
output
Yes
input
7 6
AAAAAB
ABBBAB
ABAAAB
ABABBB
ABAAAB
ABBBAB
AAAAAB
output
Yes
input
2 13
ABCDEFGHIJKLM
NOPQRSTUVWXYZ
output
No 读错题了，一直以为是要找矩形，比赛快结束才被队友提醒。
DFS一下就可以，每个点记录一下它是从起点出发的第几个点，如果搜索的过程中遇到了走过的点，那么判断一下这两个点的差是否大于等于3，如果满足就说明形成了一个环。本来想的是，如果从某个点出发没找到，那么就说明和这个点连通的所有点都不可行，于是加入了一个剪枝，将这一连通分量减掉，但是似乎没什么作用，加和不加都是15ms，网上还有一种更炫的写法，就是把起点放在当前点的屁股后面，如果遇到了走过的点就找到，我有空试试，写出来的话就更新上来。 --------------------------------------------------------------------------------------------------------- 深夜补发，刚才说的那个算法写了下，实际效果没想象的那么好，还没有我之前写的那个快，不过仔细想想，复杂度貌似是一样的。 不加剪枝：
#include <bits/stdc++.h>
using namespace std; const int UPDATE[][] = {{,},{,-},{,},{-,}};
char MAP[][];
int N,M;
struct Node
{
bool vis = ;
int n = ;
}VIS[][]; bool dfs(int,int,int,char);
int main(void)
{
cin >> N >> M; for(int i = ;i <= N;i ++)
cin >> MAP[i] + ;
for(int i = ;i <= N;i ++)
for(int j = ;j <= M;j ++)
{
VIS[i][j].vis = VIS[i][j].n = ;
if(dfs(i,j,,MAP[i][j]))
{
puts("Yes");
return ;
}
VIS[i][j].vis = VIS[i][j].n = ;
}
puts("No"); return ;
} bool dfs(int x,int y,int sum,char color)
{
for(int i = ;i < ;i ++)
{
int new_x = x + UPDATE[i][];
int new_y = y + UPDATE[i][];
if(new_x > N || new_x < || new_y > M || new_y < ||
MAP[new_x][new_y] != color)
continue; if(VIS[new_x][new_y].vis && sum - VIS[new_x][new_y].n + >= )
return true;
if(VIS[new_x][new_y].vis)
continue; VIS[new_x][new_y].vis = true;
VIS[new_x][new_y].n = sum + ;
if(dfs(new_x,new_y,sum + ,color))
return true;
VIS[new_x][new_y].vis = false;
VIS[new_x][new_y].n = sum;
} return false;
}
加了剪枝:
#include <bits/stdc++.h>
using namespace std; const int UPDATE[][] = {{,},{,-},{,},{-,}};
char MAP[][];
int N,M;
struct Node
{
bool vis = ;
int n = ;
}VIS[][]; bool dfs(int,int,int,char);
void cut(int,int,char);
int main(void)
{
cin >> N >> M; for(int i = ;i <= N;i ++)
cin >> MAP[i] + ;
for(int i = ;i <= N;i ++)
for(int j = ;j <= M;j ++)
{
if(MAP[i][j] == '.')
continue;
VIS[i][j].vis = VIS[i][j].n = ;
if(dfs(i,j,,MAP[i][j]))
{
puts("Yes");
return ;
}
VIS[i][j].vis = VIS[i][j].n = ;
cut(i,j,MAP[i][j]);
}
puts("No"); return ;
} bool dfs(int x,int y,int sum,char color)
{
for(int i = ;i < ;i ++)
{
int new_x = x + UPDATE[i][];
int new_y = y + UPDATE[i][];
if(new_x > N || new_x < || new_y > M || new_y < ||
MAP[new_x][new_y] != color)
continue; if(VIS[new_x][new_y].vis && sum - VIS[new_x][new_y].n + >= )
return true;
if(VIS[new_x][new_y].vis)
continue; VIS[new_x][new_y].vis = true;
VIS[new_x][new_y].n = sum + ;
if(dfs(new_x,new_y,sum + ,color))
return true;
VIS[new_x][new_y].vis = false;
VIS[new_x][new_y].n = sum;
} return false;
} void cut(int x,int y,char cor)
{
for(int i = ;i < ;i ++)
{
int new_x = x + UPDATE[i][];
int new_y = y + UPDATE[i][];
if(new_x > N || new_x < || new_y > M || new_y < ||
MAP[new_x][new_y] != cor || VIS[new_x][new_y].vis)
continue;
MAP[new_x][new_y] = '.';
cut(new_x,new_y,cor);
}
}
网上的算法:
#include <bits/stdc++.h>
using namespace std; const int UPDATE[][] = {{,},{,-},{,},{-,}};
int N,M;
char MAP[][];
bool VIS[][];
int BACK_X,BACK_Y; bool dfs(int i,int j,char color);
int main(void)
{
cin >> N >> M;
for(int i = ;i <= N;i ++)
cin >> MAP[i] + ;
for(int i = ;i <= N;i ++)
for(int j = ;j <= M;j ++)
{
VIS[i][j] = ;
if(dfs(i,j,MAP[i][j]))
{
puts("Yes");
return ;
}
VIS[i][j] = ;
}
puts("No"); return ;
} bool dfs(int i,int j,char color)
{
int back_x = BACK_X;
int back_y = BACK_Y;
for(int k = ;k < ;k ++)
{
int next_x = i + UPDATE[k][];
int next_y = j + UPDATE[k][]; if(next_x > N || next_x < || next_y > M || next_y < ||
MAP[next_x][next_y] != color)
continue;
if(VIS[next_x][next_y] && next_x != BACK_X && next_y != BACK_Y)
{
return true;
}
if(VIS[next_x][next_y])
continue; BACK_X = i;
BACK_Y = j;
VIS[next_x][next_y] = ;
if(dfs(next_x,next_y,color))
return true;
VIS[next_x][next_y] = ;
BACK_X = back_x;
BACK_Y = back_y;
} return false;
}