(c++)백준 16948번: 데스 나이트

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

16948번: 데스 나이트

[풀이]

최소 이동 횟수를 구하므로 bfs를 사용했다.

데스 나이트가 있는 칸에서 6방향을 모두 살펴보며 칸을 이동할 때마다 전 칸까지의 이동 횟수 + 1을 저장해둔다.

 

#include <iostream>
#include <queue>
#include <cstring>//memset
using namespace std;

struct pos {
	int r, c;
};

int N;
int r1, c1;
int r2, c2;
int visited[200][200];
const int dxy[][2] = { {-2,-1},{-2,1},{0,-2},{0,2},{2,-1},{2,1} };

void bfs() {
	queue<pos>q;
	q.push({ r1,c1 });
	visited[r1][c1] = 0;

	while (!q.empty()) {
		int r = q.front().r;
		int c = q.front().c;
		q.pop();
		for (int i = 0; i < 6; i++) {
			int nr = r + dxy[i][0];
			int nc = c + dxy[i][1];
			if (nr < 0 || nr >= N || nc < 0 || nc >= N)
				continue;
			if (visited[nr][nc] == -1 || (visited[nr][nc] > visited[r][c] + 1)) {
				visited[nr][nc] = visited[r][c] + 1;
				q.push({ nr,nc });
			}
		}
	}
}

int main() {
	cin >> N;
	cin >> r1 >> c1 >> r2 >> c2;
	memset(visited, -1, sizeof(visited));
	bfs();
	cout << visited[r2][c2] << '\n';
	return 0;
}