C++ 백준 7562번

백준 7562번 www.acmicpc.net/problem/7562

7562번: 나이트의 이동

문제 : 체스판 위에 한 나이트가 놓여 있다. 나이트가 한 번에 이동할 수 있는 칸은 아래 그림에 나와있다. 나이트가 이동하려고 하는 칸이 주어진다. 나이트는 몇 번 움직이면 이 칸으로 이동할 수 있을까?

앞에 푼 bfs문제랑 거의 똑같다!! 그냥 출발점 지정해주고 bfs를 이용해서 거리(이동 횟수)만 구해주면 된다.

테스트 케이스를 여러 번 풀어야 해서 하나 출력을 해준 뒤에 memset을 이용해서 초기화해주었다.

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
int a[301][301];
int d[301][301]; // 이동 횟수
int dx[] = { -1, -2, -2, -1, 1, 2, 2, 1 };
int dy[] = { -2, -1, 1, 2, 2, 1, -1, -2 };
int main() {
	int t;
	cin >> t;
	while (t--) {
		int l;
		cin >> l;
		for (int i = 0; i < l; i++) {
			for (int j = 0; j < l; j++) {
				d[i][j] = -1;
			}
		}
		int startx, starty;
		cin >> startx >> starty;
		a[startx][starty] = 1; // 출발점
		d[startx][starty] = 0;
		queue<pair<int, int>> q;
		q.push(make_pair(startx, starty));
		int destx, desty; // 도착점
		cin >> destx >> desty;
		
		while(!q.empty()){
			int x = q.front().first;
			int y = q.front().second;
			q.pop();
			for (int i = 0; i < 8; i++) {
				int nx = x + dx[i];
				int ny = y + dy[i];
				if (nx >= 0 && nx < l && ny >= 0 && ny < l) {
					if (a[nx][ny] == 0 && d[nx][ny] == -1 ) {
						q.push(make_pair(nx, ny));
						a[nx][ny] = 1;
						d[nx][ny] = d[x][y] + 1;
					}
				}
			}
		}
		cout << d[destx][desty] << endl;
		memset(a, 0, sizeof(a));
		memset(d, -1, sizeof(d));
	}
}