BOJ13460: 미로탈출

작성일

https://www.acmicpc.net/problem/14889

  • 1월동안 100문제 풀기 (11/100)
  • 거지같은 구현문제 치고는 그럭저럭 바로 풀었다.

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
#include <bits/stdc++.h>
using namespace std;

int N, M, depth;
vector<string> arr;
struct Point { int x, y; } red, blue, hole, none, over;
struct State { Point red, blue; };

bool eq(Point& a, Point& b) {
  return a.x == b.x && a.y == b.y;
}
bool bound(Point& a) {
  return a.x >= 0 && a.y >=0 && a.x < N && a.y < M;
}

Point move(Point& a, Point& b, int dx, int dy) {
  int mx = 0, my = 0;
  while(1) {
    int nx = a.x + dx;
    int ny = a.y + dy;
    Point np = {nx,ny};
    if(!bound(np)) return over;
    if(arr[nx][ny] == '#') break;
    if(eq(np, hole)) return a = over;
    
    if(eq(np, b)) {
      Point dOp = move(b, a, dx, dy);
      if(eq(dOp, none)) break;
    }
    a = {nx,ny}, mx += dx, my += dy;
  }
  return {mx, my};
}

int s2h(State& x) {
  return x.red.x*1000000 + x.red.y*10000 + x.blue.x*100 + x.blue.y;
}
const int dx[4] = {0,0,-1,1};
const int dy[4] = {-1,1,0,0};

int main() {
  over = {99,99};
  cin >> N >> M;
  arr.resize(N);
  for(int i =0; i < N; i++) {
    cin >> arr[i];
    for(int j = 0; j < M; j++) {
      if(arr[i][j] == 'R')      red = {i,j};
      else if(arr[i][j] == 'B') blue = {i,j};
      else if(arr[i][j] == 'O') hole = {i,j};
    }
  }

  queue<State> q;
  q.push({red, blue});
  unordered_set<int> visit;
  visit.insert(s2h(q.front()));

  while (q.size() && depth++ < 10) {
    int _size = q.size();
    for (int i = 0; i < _size; i++) {
      State cur = q.front(); q.pop();
      for(int i = 0; i < 4; i++) {
        State next = cur;
        Point dR = move(next.red, next.blue, dx[i], dy[i]);
        Point dB = move(next.blue, next.red, dx[i], dy[i]);
        if(visit.count(s2h(next))) continue;
        if(eq(dR, over) && eq(dB, over)) continue;
        if(eq(dR, over) && !eq(dB, over)) {
          cout << depth;
          return 0;
        }
        q.push({next.red, next.blue});
        visit.insert(s2h(next));
      }
    }
  }
  cout << -1;
}