[C++] 백준 7562번 - 나이트의 이동

간단한 BFS 문제이다.

오랜만에 무지성으로 풀고 한번에 통과했다

미로탐색이랑 유사한 문제이다

 

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

int	t, l, sx, sy, fx, fy;

int cnt[300][300];
bool visited[300][300];
int table[300][300];

const int dx[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
const int dy[] = { 2, 1, -1, -2, -2, -1, 1, 2 };


int main() {
	
	cin >> t;
	while (t--) {
		cin >> l;
		memset(visited, 0, sizeof(visited));
		for (int i = 0; i < l; i++) {
			for (int j = 0; j < l; j++) {
				table[i][j] = 0;
				cnt[i][j] = 0;
			}
		}

		cin >> sx >> sy;
		cin >> fx >> fy;

		queue<pair<int, int>> q;
		q.push({ sx, sy });
		visited[sx][sy] = true;
		cnt[sx][sy] = 0;
		while (!q.empty()) {
			auto current = q.front();
			q.pop();
			for (int dir = 0; dir < 8; dir++) {
				int nx = current.first + dx[dir];
				int ny = current.second + dy[dir];

				if (nx < 0 || ny < 0 || nx >= l || ny >= l)
					continue;
				if (visited[nx][ny] == true)
					continue;
				
				visited[nx][ny] = true;
				q.push({ nx, ny });
				cnt[nx][ny] = cnt[current.first][current.second] + 1;
			}
		}
		cout << cnt[fx][fy] << '\n';

	}

}