https://www.acmicpc.net/problem/17070
17070번: 파이프 옮기기 1
유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의
www.acmicpc.net
아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.
이므로! 대각선에는 조건이 하나 더 추가되야한다.
BFS 버전
|
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
77
78
79
80
81
82
83
84
85
86
87
88
|
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
int map[20][20];
int n;
int dx[] = { 1,1,0 };
int dy[] = { 0,1,1 };
struct info {
// 방향은 세로, 대각선, 가로
int x, y, d;
};
queue<info> q;
void move(int x, int y, int d, int i)
{
int nx = x + dx[i];
int ny = y + dy[i];
int nd = i;
if (map[nx][ny] == 0 && nx >= 0 && nx < n && ny >= 0 && ny < n)
{
if (i == 1)
{
if (map[nx - 1][ny] == 1 || map[nx][ny - 1] == 1)
return;
}
q.push({ nx,ny,nd });
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cin >> map[i][j];
}
int ans = 0;
q.push({ 0, 1, 2 });
while (!q.empty())
{
int x = q.front().x;
int y = q.front().y;
int d = q.front().d;
q.pop();
if (x == n - 1 && y == n - 1)
ans++;
if (d == 0) // 세로
{
for (int i = 0; i < 2; i++)
{
move(x, y, d, i);
}
}
else if (d == 1) // 대각선
{
for (int i = 0; i < 3; i++)
{
move(x, y, d, i);
}
}
else // 가로
{
for (int i = 1; i < 3; i++)
{
move(x, y, d, i);
}
}
}
cout << ans;
return 0;
}
|
cs |
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
|
#include <iostream>
#include <vector>
#include <queue>
#include <string>
using namespace std;
int map[20][20];
int n;
int ans = 0;
// 세로, 대각선, 가로
int dx[] = { 1,1,0 };
int dy[] = { 0,1,1 };
void dfs(int x, int y, int dir)
{
if (x == n - 1 && y == n - 1)
{
ans++;
return;
}
for (int i = 0; i < 3; i++)
{
if ((dir == 0 && i == 2) || (dir == 2 && i == 0))
continue;
int nx = x + dx[i];
int ny = y + dy[i];
if (map[nx][ny] == 0 && nx >= 0 && nx < n && ny >= 0 && ny < n)
{
if (i == 1)
{
if (map[nx - 1][ny] == 1 || map[nx][ny - 1] == 1)
continue;
}
dfs(nx, ny, i);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> n;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
cin >> map[i][j];
}
dfs(0, 1, 2);
cout << ans;
return 0;
}
|
cs |