[백준/c++] BOJ 18404 - 현명한 나이트

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

18404번: 현명한 나이트

 

문제 설명

NxN 크기 체스판의 특정한 위치에 하나의 나이트가 존재한다. 이때 M개의 상대편 말들의 위치 값이 주어질 때, 상대편 말을 잡기 위한 나이트의 최소 이동 수를 계산한다.

나이트는 다음과 같은 위치로 이동 가능하다.

 

N, M (1 <= N <= 500, 1 <= M <= 1,000)

나이트의 위치 X, Y (1 <= X, Y <= N)

상대편 말의 위치 A, B (1 <= A, B <= N)

해결

처음엔 상대편 말이 M개 들어오면 M BFS를 돌려 줬다. 하지만 시간 초과...

그래서 모든 상대편 말을 받은 후, N, M 체스판에 대한 BFS를 한번 돌리고, 도달한 시간은 visited 배열에 저장해 주었다.

BFS가 모두 끝난 후, 상대편 말에 대해 vistied 거리를 출력해 주면 된다.

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n, m;
pair<int, int> knight;
vector<pair<int, int>> v;
int visited[501][501];
int dx[8] = { -2, -1, 1, 2, 2, 1, -1, -2 }, dy[8] = { -1, -2, -2, -1, 1, 2, 2, 1 };

int range_over(int nx, int ny) {
	return nx < 0 || ny < 0 || ny >= n || nx >= n;
}

void bfs() {
	queue<pair<int, int>> q;
	q.push(knight);
	visited[knight.x][knight.y] = 1;

	while (!q.empty()) {
		auto cur = q.front(); q.pop();
		for (int dir = 0; dir < 8; dir++) {
			int nx = cur.x + dx[dir], ny = cur.y + dy[dir];
			if (range_over(nx, ny) || visited[nx][ny]) continue;

			visited[nx][ny] = visited[cur.x][cur.y] + 1;
			q.push({ nx, ny });
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m;
	cin >> knight.x >> knight.y;
	knight.x--, knight.y--;
	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ a - 1, b - 1 });
	}
	bfs();
	for (int i = 0; i < m; i++) {
		cout << visited[v[i].x][v[i].y] - 1 << " ";
	}
}