문제 출처 : https://www.acmicpc.net/problem/16929
16929번: Two Dots
첫째 줄에 게임판의 크기 N, M이 주어진다. 둘째 줄부터 N개의 줄에 게임판의 상태가 주어진다. 게임판은 모두 점으로 가득차 있고, 게임판의 상태는 점의 색을 의미한다. 점의 색은 알파벳 대문자 한 글자이다.
www.acmicpc.net
<C++Code>-->bool DFS
|
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
#include<iostream>
#include<string.h>
using namespace std;
char a[100][100];
int dist[100][100];
bool v[100][100];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n,m;
bool dfs(int i,int j,int cnt,char color)
{
if(v[i][j])
{
if(cnt-dist[i][j]>=4)
{
return true;
}
else
{
return false;
}
}
dist[i][j]=cnt;
v[i][j]=true;
// cout<<cnt<<' ';
for(int t=0;t<4;t++)
{
int x=i+dx[t];
int y=j+dy[t];
if(x<0||x>=n||y<0||y>=m) continue;
if(a[x][y]==color)
{
if(dfs(x,y,cnt+1,color))
{
return true;
}
}
}
return false;
}
int main(void)
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
bool finded=false;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(!v[i][j]){
memset(dist,0,sizeof(dist));
if(dfs(i,j,0,a[i][j]))
{
finded=true;
}
if(finded)
{
cout<<"Yes"<<endl;
return 0;
}
}
}
}
cout<<"No"<<endl;
return 0;
}
|
cs |
<C++Code> --> void DFS
|
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
#include<iostream>
#include<string.h>
using namespace std;
char a[100][100];
int dist[100][100];
bool v[100][100];
int dx[4]={1,-1,0,0};
int dy[4]={0,0,1,-1};
int n,m;
bool finded=false;
void dfs(int i,int j,int cnt,char color)
{
if(v[i][j])
{
if(cnt-dist[i][j]>=4)
{
finded=true;
return ;
}
else
{
return ;
}
}
dist[i][j]=cnt;
v[i][j]=true;
// cout<<cnt<<' ';
for(int t=0;t<4;t++)
{
int x=i+dx[t];
int y=j+dy[t];
if(x<0||x>=n||y<0||y>=m) continue;
if(a[x][y]==color)
{
dfs(x,y,cnt+1,color);
}
}
}
int main(void)
{
cin>>n>>m;
for(int i=0;i<n;i++)
{
cin>>a[i];
}
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
if(!v[i][j]){
memset(dist,0,sizeof(dist));
dfs(i,j,0,a[i][j]);
if(finded)
{
cout<<"Yes"<<endl;
return 0;
}
}
}
}
cout<<"No"<<endl;
return 0;
}
|
cs |
'백준 온라인 저지 > BFS, DFS (그래프)' 카테고리의 다른 글
| 16964번_DFS 스페셜 저지 (0) | 2019.12.15 |
|---|---|
| 16947번_서울 지하철 2호선 (0) | 2019.12.14 |
| 7562번_나이트의 이동(BFS) (0) | 2019.12.14 |
| 1707번_이분그래프 (0) | 2019.12.14 |
| 12851번_숨바꼭질 2 (0) | 2019.12.03 |