[BOJ] 1600. 말이 되고픈 원숭이

* 최단 거리가 정답이 아닐 수도 있다. 

*

1
3 5
0 0 0 0 0
0 0 0 0 1
0 0 0 1 0

 

처럼 도착 지점이 장애물로 막혀져있는 경우 

0 0 0 x 0
0 0 x 0 1
0 0 0 1 0

 

x로 표시되어있는 지점까지 원숭이로 이동한 후 말의 이동을 하는 방법이 도착할 수 있는 최선의 방법이다.

 

* 큐에는 4가지 값이 들어간다. 

{움직인 횟수, 말로 움직인 횟수, 좌표}

말로 움직인 횟수가 k보다 작을때까지만 말로 움직인 좌표를 큐에 넣을 수 있다. 

원숭이로 움직인 횟수는 항상 넣는다. (최단 경로 != 정답)

 

*코드가 깔끔하지 않다.

 

*dx / dy => 상하좌우

cdx / cdy => 대각선 

 

 

?

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 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152

#include <iostream> #include <vector> #include <queue> #define INF 987654321 using namespace std; int k, n, m; int map[202][202]; typedef pair<int, int> pp; typedef pair<pp, pp> pppp; bool visited[202][202][31];   int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1}; int cdx[4] = {-1, -1, 1, 1}, cdy[4] = {-1, 1, -1, 1}; int ans = INF;   bool checkRange(int x, int y) {     if (x < 0 || x >= n || y < 0 || y >= m)         return false;     return true; } void bfs() {     queue<pppp> q;       q.push(pppp(pp(0, 0), pp(0, 0)));     visited[0][0][0] = 1; //원숭이가 움직인 횟수를 저장한다.     //만약, 이 자리에 도착했을 때 이보다 더 많은 이동횟수가 필요하다면 이동하지 않는다.??       while (!q.empty())     {         int size = q.size();           while (size--)         {             int cnt = q.front().first.first;             int cntH = q.front().first.second; //말의 움직임             int x = q.front().second.first;             int y = q.front().second.second;             q.pop();               if (x == n - 1 && y == m - 1)             {                 ans = ans > cnt ? cnt : ans;                 return;             }               //말은 장애물을 뛰어넘을 수 있다.               if (cntH < k)             {                 for (int i = 0; i < 4; i++)                 {                     //말 형태로 움직일 수 있다.                     int nx = x + cdx[i];                     int ny = y + cdy[i];                       if (checkRange(nx, ny))                     {                         //이 대각선 좌표를 기준으로                         if (i == 0)                         {                             if (checkRange(nx + dx[0], ny + dy[0]) && !visited[nx + dx[0]][ny + dy[0]][cntH + 1] && !map[nx + dx[0]][ny + dy[0]])                             {                                 visited[nx + dx[0]][ny + dy[0]][cntH + 1] = 1;                                 q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[0], ny + dy[0])));                             }                             if (checkRange(nx + dx[2], ny + dy[2]) && !visited[nx + dx[2]][ny + dy[2]][cntH + 1] && !map[nx + dx[2]][ny + dy[2]])                             {                                 visited[nx + dx[2]][ny + dy[2]][cntH + 1] = 1;                                 q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[2], ny + dy[2])));                             }                         }                         if (i == 1)                         {                             if (checkRange(nx + dx[0], ny + dy[0]) && !visited[nx + dx[0]][ny + dy[0]][cntH + 1] && !map[nx + dx[0]][ny + dy[0]])                             {                                 visited[nx + dx[0]][ny + dy[0]][cntH + 1] = 1;                                 q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[0], ny + dy[0])));                             }                             if (checkRange(nx + dx[3], ny + dy[3]) && !visited[nx + dx[3]][ny + dy[3]][cntH + 1] && !map[nx + dx[3]][ny + dy[3]])                             {                                 visited[nx + dx[3]][ny + dy[3]][cntH + 1] = 1;                                 q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[3], ny + dy[3])));                             }                         }                         if (i == 2)                         {                             if (checkRange(nx + dx[1], ny + dy[1]) && !visited[nx + dx[1]][ny + dy[1]][cntH + 1] && !map[nx + dx[1]][ny + dy[1]])                             {                                 visited[nx + dx[1]][ny + dy[1]][cntH + 1] = 1;                                 q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[1], ny + dy[1])));                             }                             if (checkRange(nx + dx[2], ny + dy[2]) && !visited[nx + dx[2]][ny + dy[2]][cntH + 1] && !map[nx + dx[2]][ny + dy[2]])                             {                                 visited[nx + dx[2]][ny + dy[2]][cntH + 1] = 1;                                 q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[2], ny + dy[2])));                             }                         }                         if (i == 3)                         {                             if (checkRange(nx + dx[1], ny + dy[1]) && !visited[nx + dx[1]][ny + dy[1]][cntH + 1] && !map[nx + dx[1]][ny + dy[1]])                             {                                 visited[nx + dx[1]][ny + dy[1]][cntH + 1] = 1;                                 q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[1], ny + dy[1])));                             }                             if (checkRange(nx + dx[3], ny + dy[3]) && !visited[nx + dx[3]][ny + dy[3]][cntH + 1] && !map[nx + dx[3]][ny + dy[3]])                             {                                 visited[nx + dx[3]][ny + dy[3]][cntH + 1] = 1;                                 q.push(pppp(pp(cnt + 1, cntH + 1), pp(nx + dx[3], ny + dy[3])));                             }                         }                     }                 }             }             for (int j = 0; j < 4; j++)             {                 //원숭이 움직임                 int cx = x + dx[j];                 int cy = y + dy[j];                   if (checkRange(cx, cy) && !visited[cx][cy][cntH] && !map[cx][cy])                 {                     visited[cx][cy][cntH] = 1;                     q.push(pppp(pp(cnt + 1, cntH), pp(cx, cy)));                 }             }         }     } } int main() {       ios_base::sync_with_stdio(0);     cin.tie(0);       cin >> k >> m >> n;       for (int i = 0; i < n; i++)     {         for (int j = 0; j < m; j++)         {             cin >> map[i][j];         }     }     bfs();     if (ans == INF)         cout << -1 << '\n';     else         cout << ans << '\n';     return 0; }