[BFS] 백준7562 나이트의 이동

www.acmicpc.net/problem/7562

7562번: 나이트의 이동

수행 시간 : 1시간

전형적인 BFS 문제이다. dx, dy의 좌표를 -2,-1,1,2 4개로 표현 해주면 쉽게풀린다.

 

++ 앞으로 bfs안에서 뭔가를 세줘야되면 queue에 넣어서 넘겨주는게 에러안나고 훨씬 편하다는걸 알게되었다.

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

int n, l;
vector <int> ans;
bool visited[301][301];
int nx, ny;
int dx[8] = { 1,2,2,1,-1,-2,-2,-1 };
int dy[8] = { -2,-1,1,2,2,1,-1,-2 };

int bfs(int x, int y) {
	memset(visited, 0, sizeof(visited));
	int cnt = 0;
	queue < pair<pair<int, int>, int>> q;
	visited[x][y] = true;
	q.push(make_pair(make_pair(x, y), 0));
	while (!q.empty()) {
		int a = q.front().first.first;
		int b = q.front().first.second;
		int cnt = q.front().second;
		q.pop();
		if (a == nx && b == ny) {
			return cnt;
		}
		for (int i = 0;i < 8;i++) {
			int na = dx[i] + a;
			int nb = dy[i] + b;
			if (na >= 0 && na < l && nb >= 0 && nb < l) {
				if (visited[na][nb] == false) {
					visited[na][nb] = true;
					q.push(make_pair(make_pair(na, nb), cnt + 1));
				}
			}
		}
	}
}

int main() {
	cin >> n;
	ans.resize(n);
	for (int k = 0;k < n;k++) {
		int x, y;
		cin >> l;
		cin >> x >> y >> nx >> ny;
		ans[k] = bfs(x,y);
	}
	for (int i = 0;i < n;i++) {
		cout << ans[i] << "\n";
	}
}