백준(BOJ) 1600번 말이 되고픈 원숭이

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

1600번: 말이 되고픈 원숭이

풀이 :

queue에 K의 수만큼 같이 넣어주자. K가 0보다 크다면 말처럼 이동할 수 있으므로 말처럼 이동하는 8가지 경우의 수를

 

추가로 넣어주자. 

 

코드 (C ++ )

 

	#include <iostream>
	#include <vector>
	#include <queue>
	using namespace std;
	int board[200][200];
	int dis[200][200][31];
	int h, w;
	int k;
	const int dy[4] = { 1,-1,0,0 };
	const int dx[4] = { 0, 0,1,-1 };
	const int hy[8] = { -2,-1,1,2,2,1,-1,-2 };
	const int hx[8] = { 1, 2,2,1,-1,-2,-2,-1 };
	int main()
	{
	cin >> k;
	cin >> w >> h;
	for (int i = 0; i < h; ++i)
	for (int j = 0; j < w; ++j)
	{
	cin >> board[i][j];
	}
	queue<pair<pair<int, int>, int>> q;
	q.push({ {0,0},k });
	dis[0][0][k] = 0;
	while (!q.empty())
	{
	int y = q.front().first.first;
	int x = q.front().first.second;
	int cnt = q.front().second;
	q.pop();
	if (cnt > 0)
	{
	for (int i = 0; i < 8; ++i)
	{
	int ny = y + hy[i];
	int nx = x + hx[i];
	if (!(ny >= 0 && ny < h && nx >= 0 && nx < w)) continue;
	if (board[ny][nx] == 1 || dis[ny][nx][cnt - 1]) continue;
	dis[ny][nx][cnt - 1] = dis[y][x][cnt] + 1;
	q.push({ {ny,nx},cnt - 1 });
	}
	}
	for (int i = 0; i < 4; ++i)
	{
	int ny = y + dy[i];
	int nx = x + dx[i];
	if (!(ny >= 0 && ny < h && nx >= 0 && nx < w)) continue;
	if (board[ny][nx] == 1 || dis[ny][nx][cnt]) continue;
	dis[ny][nx][cnt] = dis[y][x][cnt] + 1;
	q.push({ {ny,nx},cnt });
	}
	}
	int ret = -1;
	for (int i = 0; i <= k; ++i)
	{
	if (dis[h - 1][w - 1][i] == 0) continue;
	if (ret == -1) {
	ret = dis[h - 1][w - 1][i];
	}
	else if (ret > dis[h - 1][w - 1][i]) {
	ret = dis[h - 1][w - 1][i];
	}
	}
	cout << ret << "\n";
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub