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

http://acmicpc.net/problem/1600

[풀이방법] 

BFS로 풀이를 하였고, [남아있는 점프횟수][R][C] 에 갈 수 있는 위치의 값을 갱신한다. 

다른 위치로 진행하는 방법은 

1. move (상하좌우) 이 경우 남아있는 점프횟수가 0이상인 경우에 가능하다. 큐에 넣을 때는 남아있는 점프횟수를 깎지 않아도 된다.
2. jump(체스의 나이트의 이동)으로 한다. 이 경우 남아있는 점프횟수가 1이상인 경우에 가능하다. 이 경우 큐에 넣을 때 현재점프가능횟수-1을 해야한다. 

vis[남아있는 점프횟수][ROW][COL] 로 점프할 수 있다. 

남아있는 점프횟수가 있는 경우 jump 를 진행한다. 

그렇게 되면 도착지에 최소값이 갱신이 된다.

[C++11]

#include<cstdio>
#include<queue>
#include<memory.h>
using namespace std;
const int m = 201;
const int kn = 31;
int K;
int row, col;
int im[m][m];
int vis[kn][m][m];
const int dr[] = { 0,1,0,-1 };
const int dc[] = { 1,0,-1,0 };
const int jr[] = { -2,-2,-1,-1,1,1,2,2 }; // 계속 틀린이유...
const int jc[] = { -1,1,-2,2,-2,2,-1,1 };
const int INF = 1 << 22;
struct pos {
    int r, c;
    int jump;
    pos() {}
    pos(int ir, int ic, int ij) :r(ir), c(ic), jump(ij) {}
};
int main() {
    scanf("%d", &K);
    scanf("%d%d", &col, &row);
    for (int r = 0; r < row; r++) {
        for (int c = 0; c < col; c++) {
            scanf("%d", &im[r][c]);
        }
    } // input
    //memset(vis, -1, sizeof(vis)); // init
    queue<pos> Q;
    Q.push(pos(0, 0, K));
    vis[K][0][0] = 1;
    while (!Q.empty()) {
        pos here = Q.front();
        Q.pop();
        int hr = here.r;
        int hc = here.c;
        int hj = here.jump;
        for (int i = 0; i < 4; i++) {
            int tr = hr + dr[i];
            int tc = hc + dc[i];
            if (tr < 0 || row <= tr || tc < 0 || col <= tc) continue;
            if (im[tr][tc] == 1) continue;
            if (vis[hj][tr][tc] == 0) {
                vis[hj][tr][tc] = vis[hj][hr][hc] + 1;
                Q.push(pos(tr, tc, hj));
            }
        }// move
        if (hj > 0) {
            for (int i = 0; i < 8; i++) {
                int tr = hr + jr[i];
                int tc = hc + jc[i];
                if (tr < 0 || row <= tr || tc < 0 || col <= tc) continue;
                if (im[tr][tc] == 1) continue;
                if (vis[hj - 1][tr][tc] == 0) {
                    vis[hj - 1][tr][tc] = vis[hj][hr][hc] + 1;
                    Q.push(pos(tr, tc, hj - 1));
                }
            }// jump
        }
    }
    int ans = INF;
    for (int i = 0; i <= K; i++) {
        if (vis[i][row - 1][col - 1] != 0) {
            ans = (vis[i][row - 1][col - 1] > ans ) ? ans : vis[i][row - 1][col - 1];
        }        
    }
    printf("%d\n", (ans == INF) ? -1 : ans-1);
    return 0;
}