말이 되고픈 원숭이

• 벽부수고 이동하기 와 매우 유사한 문제

코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define INF 1e9
using namespace std;
int board[201][201];
int cost[31][201][201];
int hx[8] = {2, 2, 1, 1, -1, -1, -2, -2};
int hy[8] = {1, -1, 2, -2, 2, -2, 1, -1};
int dx[4] = {0, 1, 0, -1};
int dy[4] = {1, 0, -1, 0};
queue<pair<pair<int,int>,int>> q;
int ans=INF;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int W, H, K;
    cin >> K;
    cin >> W >> H;
    for(int i=0;i<H;i++)
        for(int j=0;j<W;j++)
            cin >> board[i][j];

    for(int k=0;k<K+1;k++)
        for(int i=0;i<H;i++)
            for(int j=0;j<W;j++)
                cost[k][i][j] = INF;

    for(int k=0;k<K+1;k++)
        cost[k][0][0] = 0;
    q.push({{0,0},0});
    while(!q.empty())
    {
        auto cur = q.front(); q.pop();
        if(cur.second < K)
        {
            for(int dir=0;dir<8;dir++)
            {
                int ny = cur.first.first + hy[dir];
                int nx = cur.first.second + hx[dir];
                int status = cur.second;
                if(nx<0 or ny<0 or nx>=W or ny>=H) continue;
                if(board[ny][nx] == 1) continue;
                /* 같을 때에도 pass해야함 안그러면 큐에 무한히 쌓임 */
                if(cost[status+1][ny][nx] <= cost[cur.second][cur.first.first][cur.first.second] + 1) continue;
                cost[status+1][ny][nx] = cost[cur.second][cur.first.first][cur.first.second] + 1;
                q.push({{ny,nx},status+1});
            }
        }
        for(int dir=0;dir<4;dir++)
        {
            int ny = cur.first.first + dy[dir];
            int nx = cur.first.second + dx[dir];
            int status = cur.second;
            if(nx<0 or ny<0 or nx>=W or ny>=H) continue;
            if(board[ny][nx] == 1) continue;
            /* 같을 때에도 pass해야함 안그러면 큐에 무한히 쌓임 */
            if(cost[status][ny][nx] <= cost[cur.second][cur.first.first][cur.first.second] + 1) continue;
            cost[status][ny][nx] = cost[cur.second][cur.first.first][cur.first.second] + 1;
            q.push({{ny,nx},status});
        }
    }
    for(int k=0;k<K+1;k++)
        ans = min(ans, cost[k][H-1][W-1]);
    if(ans == INF) cout << -1;
    else cout << ans;
    return 0;
}

• 핵심
  • 이 문제 역시 cost[K][H][W]로 각 칸에서 말처럼 가는 능력을 K번 쓰고 온 경우를 모두 계산
  • 주의할 점
    : cost[K][H][W] 비교할 때 같으면 큐에 무한히 쌓여서 메모리 초과가 된다 !!!