#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;
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;
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]
비교할 때 같으면
큐에 무한히 쌓여서 메모리 초과
가 된다 !!!