[백준/BOJ] 1600번 말이 되고픈 원숭이 (C++)

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

1600번: 말이 되고픈 원숭이

2206번 벽 부수고 이동하기를 응용한 것 같은 문제였다. 해당 문제를 해결했다면 어렵지 않았을 BFS 문제다.

#include <iostream>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;

struct Pos {
	int x, y, cnt;
};

int k, w, h;
int map[201][201];
int visit[31][201][201];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int hx[8] = {-2, -2, -1, 1, 2, 2, -1, 1};
int hy[8] = {-1, 1, -2, -2, -1, 1, 2, 2};

int BFS() {
	queue<Pos> q;
	q.push({ 0, 0, k });
	visit[k][0][0] = 0;
	
	while(!q.empty()) {
		int x = q.front().x;
		int y = q.front().y;
		int cnt = q.front().cnt;
		q.pop();
		
		if(x == h - 1 && y == w - 1) return visit[cnt][x][y];
		
		if(cnt > 0) {
			for(int i = 0; i < 8; i++) {
				int nx = x + hx[i];
				int ny = y + hy[i];
				if(nx >= 0 && nx < h && ny >= 0 && ny < w) {
					if(visit[cnt - 1][nx][ny] == -1 && map[nx][ny] == 0) {
						q.push({ nx, ny, cnt - 1 });
						visit[cnt - 1][nx][ny] = visit[cnt][x][y] + 1;
					}
				}
			}
		}
		
		for(int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(nx >= 0 && nx < h && ny >= 0 && ny < w) {
				if(visit[cnt][nx][ny] == -1 && map[nx][ny] == 0) {
					q.push({ nx, ny, cnt });
					visit[cnt][nx][ny] = visit[cnt][x][y] + 1;
				}
			}
		}
	}
	
	return -1;
}

int main(void) {
	//freopen("input.txt", "rt", stdin);
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> k >> w >> h;
	for(int i = 0; i < h; i++) {
		for(int j = 0; j < w; j++) {
			cin >> map[i][j];
		}
	}
	
	memset(visit, -1, sizeof(visit));
	cout << BFS();
}