[백준/BOJ] 16948번 데스 나이트 (C++)

www.acmicpc.net/problem/16948

16948번: 데스 나이트

BFS를 통해 해결할 수 있는 간단한 문제였습니다.

 

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

int n, r1, c1, r2, c2;
int map[201][201];
int dx[6] = {-2, -2, 0, 0, 2, 2};
int dy[6] = {-1, 1, -2, 2, -1, 1};

int BFS() {
	memset(map, -1, sizeof(map));
	queue<pair<int, int > > q;
	map[r1][c1] = 0;
	q.push({ r1, c1 });
	
	while(!q.empty()) {
		int x = q.front().first;
		int y = q.front().second;
		q.pop();
		if(x == r2 && y == c2) return map[x][y];
		
		for(int i = 0; i < 6; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];
			if(map[nx][ny] != -1 || nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
			map[nx][ny] = map[x][y] + 1;
			q.push({ nx, ny });
		}
	}
	
	return -1;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	
	cin >> n >> r1 >> c1 >> r2 >> c2;
	cout << BFS();
}