[백준 1600번] 말이 되고픈 원숭이

소스코드

---

#include <iostream>
using namespace std;
 
struct position {
    int x;
    int y;
    int cnt;
};
 
int k, w, h, map[215][215],v[35][215][215],chk[215][215];
int mdx[4] = { 0, 0, -1, 1 };
int mdy[4] = { -1, 1, 0, 0 };
int hdx[8] = {-1,-2,-2,-1,1,2,2,1};
int hdy[8] = {-2,-1,1,2,2,1,-1,-2};
position pos[1500000];
int head, tail;
 
void bfs() {
    while (head != tail) {
        int curX = pos[head].x;
        int curY = pos[head].y;
        int curCnt = pos[head].cnt;
 
        if (curX == h - 1 && curY == w - 1) {
            cout << chk[curX][curY] << '\n';
            return;
        }
 
        for (int i = 0; i < 4; i++) {
            int xx = curX + mdx[i];
            int yy = curY + mdy[i];
            if (xx < 0 || xx >= h || yy < 0 || yy >= w) { continue; }
            if (!map[xx][yy] && !v[curCnt][xx][yy]) {
                v[curCnt][xx][yy] = 1;
                pos[tail].x = xx;
                pos[tail].y = yy;
                pos[tail].cnt = curCnt;
                chk[xx][yy] = chk[curX][curY] + 1;
                tail++;
            }
        }
 
        if (curCnt>0) {
            for (int i = 0; i < 8; i++) {
                int xx = curX + hdx[i];
                int yy = curY + hdy[i];
                if (xx < 0 || xx >= h || yy < 0 || yy >= w) { continue; }
                if (!map[xx][yy] && !v[curCnt-1][xx][yy]) {
                    v[curCnt-1][xx][yy] = 1;
                    pos[tail].x = xx;
                    pos[tail].y = yy;
                    pos[tail].cnt = curCnt - 1;
                    chk[xx][yy] = chk[curX][curY] + 1;
                    tail++;
                }
            }
        }
 
        head++;
    }
    cout << -1 << '\n';
}
 
 
 
int main() {
    cin >> k >> w >> h;
    for (int i = 0; i < h; i++)
        for (int j = 0; j < w; j++)
            cin >> map[i][j];
    pos[0].x = 0, pos[0].y = 0, pos[0].cnt = k;
    v[k][0][0] = 1;
    head = 0, tail = 1;
    bfs();
    return 0;
}