1600 말이 되고픈 원숭이

문제 링크

• 내 풀이

지도에 점프 가능한 횟수를 저장한다. 자신의 점프 가능한 횟수보다 큰 곳은 진입하지 않는다. 왜냐하면 점프하는 것이 더 빠르기 때문 문제에서 정해진 최대 점프 횟수 + 1을 벽으로 저장한다. 빈 공간은 -1로 하여 0번 점프가 가능해도 갈 수 있게 한다.

#include <iostream>
#include <queue>

#define pii pair<int,int>

using namespace std;

int K, W, H;
int m[200][200];

int mr[4] = { -1,  1,  0,  0 };
int mc[4] = {  0,  0, -1,  1 };
int hr[8] = { -1, -2, -2, -1,  1,  2,  2,  1 };
int hc[8] = { -2, -1,  1,  2, -2, -1,  1,  2 };

int solve()
{
    queue<pii> q;
    q.push({ 0, 0 });
    m[0][0] = K;

    int ret = 0;

    while (!q.empty())
    {
        int sz = q.size();
        while (sz--)
        {
            int r = q.front().first;
            int c = q.front().second;
            q.pop();

            if (r == H - 1 && c == W - 1)
                return ret;

            for (int d = 0; d < 4; d++)
            {
                int nr = r + mr[d];
                int nc = c + mc[d];

                if (nr < 0 || nr >= H || nc < 0 || nc >= W || m[nr][nc] >= m[r][c])
                    continue;

                q.push({ nr, nc });
                m[nr][nc] = m[r][c];
            }

            if (m[r][c])
            {
                for (int d = 0; d < 8; d++)
                {
                    int nr = r + hr[d];
                    int nc = c + hc[d];

                    if (nr < 0 || nr >= H || nc < 0 || nc >= W || m[nr][nc] >= (m[r][c] - 1))
                        continue;

                    q.push({ nr, nc });
                    m[nr][nc] = m[r][c] - 1;
                }
            }
        }
        ret += 1;
    }

    return -1;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> K;
    cin >> W >> H;

    int t;
    for (int h = 0; h < H; h++)
    {
        for (int w = 0; w < W; w++)
        {
            cin >> t;
            if (t)
                m[h][w] = 31;
            else
                m[h][w] = -1;
        }
    }

    cout << solve() << "\n";
    return 0;
}