백준알고리즘
통나무 옮기기
먼지의삶
2019. 9. 27. 20:42
|
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
#include<iostream>
#include<queue>
#include<utility>
using namespace std;
struct P{
int x, y, rot;
P(int x, int y, int rot) {
this->x = x;
this->y = y;
this->rot = rot;
}
};
int n;
string map[51];
bool d[51][51][2];
int ex = 0, ey = 0;
int dist[51][51][2];
int ans = 987654321;
bool findd = false;
int dx[] = { 0,0,1,-1 };
int dy[] = { 1,-1,0,0 };
void bfs(int x, int y, int rot) {
queue<P> q;//rot = 1 1 rot = 0 ㅡ
q.push(P(x,y,rot));
d[x][y][rot] = true;
while (!q.empty()) {
x = q.front().x; y = q.front().y; rot = q.front().rot;
q.pop();
for (int i = 0; i < 5; i++) {
if (i < 4) {
int nx = x + dx[i]; int ny = y + dy[i];
if (rot == 0) {
if (nx >= 0 && nx < n && ny > 0 && ny < n - 1) {
if ((map[nx][ny] =='0'||map[nx][ny]=='B'||map[nx][ny]=='E')&& ny> 0 && ny < n-1&&
(map[nx][ny + 1] == '0' || map[nx][ny + 1] == 'B' ||map[nx][ny+1]=='E') &&
(map[nx][ny - 1] == '0' || map[nx][ny - 1] == 'B'||map[nx][ny-1]=='E')&&d[nx][ny][rot]==false) {
d[nx][ny][rot] = true;
dist[nx][ny][rot] = dist[x][y][rot] + 1;
if (map[nx][ny] == 'E' && map[nx][ny - 1] == 'E' && map[nx][ny + 1] == 'E') {
if (ans > dist[nx][ny][rot]) {
ans = dist[nx][ny][rot]; findd = true;
}
}
q.push(P(nx, ny, rot));
}
}
}
else if(rot == 1) {
if (nx > 0 && nx < n - 1 && ny >= 0 && ny < n) {
if ((map[nx][ny] == '0' || map[nx][ny] == 'B' || map[nx][ny] == 'E') && nx > 0
&& nx < n-1 &&(map[nx + 1][ny] == '0' || map[nx + 1][ny] == 'B'||map[nx+1][ny]=='E') &&
(map[nx - 1][ny] == '0' || map[nx - 1][ny] == 'B'||map[nx-1][ny]=='E') &&d[nx][ny][rot]==false) {
d[nx][ny][rot] = true;
dist[nx][ny][rot] = dist[x][y][rot] + 1;
if (map[nx][ny] == 'E' && map[nx-1][ny] == 'E' && map[nx+1][ny] == 'E') {
if (ans > dist[nx][ny][rot]) { ans = dist[nx][ny][rot]; findd = true; }
}
q.push(P(nx, ny, rot));
}
}
}
}
else {
if (rot == 0 && d[x][y][1] == false && x>0 && x<n-1 && (map[x + 1][y] == '0' || map[x + 1][y] == 'B'
|| map[x + 1][y] == 'E') &&
(map[x - 1][y] == '0' || map[x - 1][y] == 'B' || map[x - 1][y] == 'E') &&(map[x + 1][y + 1] == '0'
|| map[x + 1][y + 1] == 'B' || map[x + 1][y + 1] == 'E') && (map[x - 1][y + 1] == '0' || map[x - 1][y + 1] == 'B' || map[x - 1][y + 1] == 'E')
&& (map[x - 1][y - 1] == '0' || map[x - 1][y - 1] == 'B' || map[x - 1][y - 1] == 'E') && (map[x + 1][y - 1] == '0' || map[x + 1][y - 1] == 'B' || map[x + 1][y - 1] == 'E')) {
d[x][y][1] = true;
dist[x][y][1] = dist[x][y][0] + 1;
if (x > 0 && x < n-1 && map[x][y] == 'E' && map[x - 1][y] == 'E' && map[x + 1][y] == 'E') {
if (ans > dist[x][y][1]) { ans = dist[x][y][1]; findd = true; }
}
q.push(P(x, y, 1));
}
else if (rot == 1 && d[x][y][0] == false && y>0 && y<n-1&&(map[x][y + 1] == '0' || map[x][y + 1] == 'B' || map[x][y + 1] == 'E') &&
(map[x][y - 1] == '0' || map[x][y - 1] == 'B' || map[x][y - 1] == 'E') && (map[x + 1][y + 1] == '0' || map[x + 1][y + 1] == 'B' || map[x + 1][y + 1] == 'E') && (map[x - 1][y + 1] == '0' || map[x - 1][y + 1] == 'B' || map[x - 1][y + 1] == 'E')
&& (map[x - 1][y - 1] == '0' || map[x - 1][y - 1] == 'B' || map[x - 1][y - 1] == 'E') && (map[x + 1][y - 1] == '0' || map[x + 1][y - 1] == 'B' || map[x + 1][y - 1] == 'E')) {
d[x][y][0] = true;
dist[x][y][0] = dist[x][y][1] + 1;
if (y> 0 && y< n-1&&map[x][y] == 'E' && map[x][y - 1] == 'E' && map[x][y + 1] == 'E') {
if (ans > dist[x][y][0]) { ans = dist[x][y][0]; findd= true; }
}
q.push(P(x,y, 0));
}
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n;
for (int i = 0; i < n; i++) {
cin >> map[i];
}
int cnt = 0;
int ent = 0;
int cx = 0, cy = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (map[i][j] == 'B') {
cnt++;
if (cnt == 2) {
cx = i; cy = j;
}
}
if (map[i][j] == 'E') {
ent++;
if (ent == 2) {
ex = i; ey = j;
}
}
}
}
int rot = 0;
if (cx >= 1 && cx <n-1 && map[cx - 1][cy] == 'B' && map[cx + 1][cy] == 'B') {
rot = 1;
}
else if (cy>= 1 && cy<n-1&& map[cx][cy + 1] == 'B' && map[cx][cy - 1] == 'B') {
rot = 0;
}
bfs(cx, cy, rot);
if (findd)
cout << ans << '\n';
else cout << 0 << '\n';
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
BFS문제, 어렵다 라기보다는 문제를 잘읽고풀어야한다는것이 좀더 기억에 남는 문제,
다른것보다도 돌아가는것을 3x3전체에 비어있어야한다는 조건을 잊고 돌려버리면 무조건틀리는문제다.