통나무 옮기기

*시뮬레이션

*통나무는 중간에 있는 좌표와 현재 방향(세로/가로)의 상태만 저장한다.

 

#include <iostream> #include <vector> #include <queue> #define INF 987654321 using namespace std; typedef pair < int, int > pp; typedef pair < pp, int > ppi; typedef pair < pp, pp > pppp; int n, ans = INF; char map[51][51]; ppi treeB, treeE; bool visited[51][51][2]; int dx[4] = { -1,1,0,0 }, dy[4] = { 0,0,-1,1 }; int cdx[8] = { -1,-1,-1,0,0,1,1,1 }, cdy[8] = { -1,0,1,-1,1,-1,0,1 }; bool check(int x, int y, int dir, int n_dir) { if (n_dir < 2) { //남 북 if (dir == 1) { if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y][dir] ) return false; else return true; } else if (dir == 0) { //내 위 아래 인덱스가 빠져나갈 가능성을 생각하낟. if (x <= 0 || x >= n - 1 || y < 0 || y >= n || visited[x][y][dir]) return false; else return true; } } else { //동서 if (dir == 1) { if (x < 0 || x >= n || y <= 0 || y >= n-1 || visited[x][y][dir]) return false; else return true; } else if (dir == 0) { //내 위 아래 인덱스가 빠져나갈 가능성을 생각하낟. if (x < 0 || x >= n || y < 0 || y >= n || visited[x][y][dir]) return false; else return true; } } } void bfs() { queue < pppp > q; q.push(pppp(pp(0, treeB.second), treeB.first)); visited[treeB.first.first][treeB.first.second][treeB.second] = true; while (!q.empty()) { int size = q.size(); while (size--) { int x = q.front().second.first; int y = q.front().second.second; int cnt = q.front().first.first; int dir = q.front().first.second; q.pop(); //통나무 중간위치의 좌표 //x, y기준으로 가르키는 방향으로 위아래 / 양옆으로 더 있다. //회전할 수 있는 기준은 중간 통나무 기준으로 3*3이 비어있어야 한다. if (x == treeE.first.first && y == treeE.first.second && dir == treeE.second) { ans = min(ans, cnt); continue; } for (int i = 0; i < 4; i++) { int nx = x + dx[i]; int ny = y + dy[i]; if (check(nx, ny, dir, i)) { //가는 방향으로 나무가 잇는 지 확인한다. if (dir == 0) { if (i == 0) { //북 //내 위에 위에가 나무인지 확인한다. if (map[nx - 1][ny] == '1') continue; } else if (i == 1) { if (map[nx + 1][ny] == '1' ) continue; } else if (i == 2 || i == 3) { //서 //세 군데 모두 살펴봐야 한다. if (map[nx][ny] == '1' || map[nx-1][ny] == '1' || map[nx + 1][ny] == '1') continue; } } else if (dir == 1) { if (i == 0 || i == 1) { if (map[nx][ny] == '1' || map[nx][ny - 1] == '1' || map[nx][ny + 1] == '1') continue; } else if (i == 2) { //서쪽 if (map[nx][ny - 1] == '1') continue; } else if (i == 3) { if (map[nx][ny + 1] == '1') continue; } } // 모두 통과한 경우 visited[nx][ny][dir] = true; q.push(pppp(pp(cnt + 1, dir), pp(nx, ny))); } } //방향전환 //3*3안에 아무것도 없어야 한다. bool flag = true; for (int i = 0; i < 8; i++) { int nx = x + cdx[i]; int ny = y + cdy[i]; if (nx < 0 || nx >= n || ny < 0 || ny >= n || map[nx][ny] == '1') { flag = false; break; } } if (flag) { int n_dir = 1 - dir; if (visited[x][y][n_dir]) continue; visited[x][y][n_dir] = true; q.push(pppp(pp(cnt + 1, n_dir), pp(x, y))); } } } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); //통나무는 중간의 좌표와 방향만 저장한다. cin >> n; bool flagB = false, flagE = false; for (int i = 0; i < n; i++) { string s; cin >> s; for (int j = 0; j < n; j++) { map[i][j] = s[j]; } } for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { if (map[i][j] == 'B' && !flagB) { if (map[i][j + 1] == 'B') { //가로 방향 treeB = ppi(pp(i, j+1), 1); } else if (map[i + 1][j] == 'B') { treeB = ppi(pp(i+1, j), 0); } flagB = true; } if (map[i][j] == 'E' && !flagE) { if (map[i][j + 1] == 'E') { //가로 방향 treeE = ppi(pp(i, j+1), 1); } else if (map[i + 1][j] == 'E') { treeE = ppi(pp(i+1, j), 0); } flagE = true; } } } bfs(); if (ans == INF) cout << 0 << '\n'; else cout << ans << '\n'; return 0; }