1600 말이 되고픈 원숭이

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

원숭이가 격자판의 왼쪽 맨 위에서 오른쪽 맨 아래로 이동하려고 한다. 이동하는 방법은 두 가지가 있다. 일반적인 동서남북 이동과 체스에서의 말의 이동이다. 말의 이동은 최대 K번 까지 할 수 있다. 이 때, 목적지까지 갈 수 없다면 -1를 출력하고 아니면 이동 횟수의 최소값을 출력하는 문제이다.

일반적인 BFS에서의 이동과는 다르게 말의 이동이 추가되어 있다. 그리고 이동할 때마다 말의 이동 가능 횟수가 줄어든다. 현재 위치에서의 남은 말의 이동 가능 횟수가 다르면 다른 상태로 보고 visit 배열을 3차원으로 선언해준다. visit[x][y][k] = 현재위치가 (x,y)이고 남은 말의 이동 횟수가 k일 때 방문했는가? 큐의 크기만큼 매번 빼주면서 depth를 세면서 처음 목적지에 도달하게 되면 그 때 depth가 이동 횟수의 최소값이다.

#include <cstdio>
#include <queue>
using namespace std;
 
int k,w,h,map[200][200];
bool v[200][200][31];
int dx[4]={0,0,-1,1},dy[4]={-1,1,0,0};
int hx[8]={-2,-2,-1,-1,1,1,2,2};
int hy[8]={-1,1,-2,2,-2,2,-1,1};
struct S { int x,y,k; };
 
void bfs()
{
    queue<S> q;
    q.push({0,0,k}); // 현재 좌표, 남은 말의 이동방법 횟수
    v[0][0][k]=true; // 방문표시
 
    int depth=1;
    while(!q.empty())
    {
        int size=q.size();
        while(size--)
        {
            auto now=q.front(); q.pop();
            int x=now.x,y=now.y,k=now.k;
 
            for(int i=0;i<4;i++)
            {
                int nx=x+dx[i],ny=y+dy[i];
                if(nx<0 || nx>=h || ny<0 || ny>=w) continue;
                if(nx==h-1 && ny==w-1)
                {
                    printf("%d",depth);
                    return;
                }
                if(!map[nx][ny] && !v[nx][ny][k])
                {
                    v[nx][ny][k]=true;
                    q.push({nx,ny,k});
                }
            }
 
            if(k==0) continue;
 
            for(int i=0;i<8;i++)
            {
                int nx=x+hx[i],ny=y+hy[i];
                if(nx<0 || nx>=h || ny<0 || ny>=w) continue;
                if(nx==h-1 && ny==w-1)
                {
                    printf("%d",depth);
                    return;
                }
                if(!map[nx][ny] && !v[nx][ny][k-1])
                {
                    v[nx][ny][k-1]=true;
                    q.push({nx,ny,k-1});
                }
            }
        }
        depth++;
    }
 
    printf("-1\n");
}
 
int main()
{
    scanf("%d %d %d",&k,&w,&h); // w:가로 h:세로
    for(int i=0;i<h;i++) for(int j=0;j<w;j++) scanf("%d",&map[i][j]);
    bfs();
    return 0;
}