백준 16948번 데스 나이트

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

16948번: 데스 나이트

 

 

 

 

 

<접근방법>

bfs 문제입니다.

이 문제는 이동방향이 상, 하, 좌, 우가 아닙니다.

문제에서 주어진대로 이동방향을 정의하면 됩니다.

 

 

<느낀 점>

 

 

 

---

 

 

 

<코드>

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

struct point {
	int y, x;
};

int n, ay, ax, by, bx, map[200][200], res;
bool visit[200][200];
int dy[6] = {-2, -2, 0, 0, 2, 2};
int dx[6] = {-1, 1, -2, 2, -1, 1};

queue<point> q;

int bfs() {
	q.push({ay, ax});
	visit[ay][ax] = true;

	while (!q.empty()) {
		int sz = q.size();
		while (sz--) {
			point t = q.front();
			q.pop();

			if (t.y == by && t.x == bx) {
				return res;
			}

			for (int i = 0; i < 6; i++) {
				int ny = t.y + dy[i];
				int nx = t.x + dx[i];

				if (ny < 0 || nx < 0 || ny >= n || nx >= n
					|| visit[ny][nx]) continue;
				visit[ny][nx] = true;
				q.push({ ny, nx});
			}
		}
		res++;
	}
	return -1;
}

int main() {
	cin >> n;
	cin >> ay >> ax >> by >> bx;

	if (ay == by && ax == bx) {
		cout << 0 << '\n';
		exit(0);
	}

	cout << bfs() << '\n';
	return 0;
}