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

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

7562번: 나이트의 이동

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

int main() {
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);
	int testCase;
	cin >> testCase;
	for (int t = 0; t < testCase; t++) {
		int l;
		cin >> l;
		int nowRow, nowCol;
		int destRow, destCol;
		cin >> nowRow >> nowCol >> destRow >> destCol;
		int count;
		tuple<int, int, int> now = make_tuple(nowRow, nowCol, 0);
		queue<tuple<int, int, int>> q;
		vector<vector<bool>> visited(l, vector<bool>(l));
		q.push(now);
		while (!q.empty()) {
			tuple<int, int, int> cur = q.front();
			q.pop();
			if (!visited[get<0>(cur)][get<1>(cur)]) {
				visited[get<0>(cur)][get<1>(cur)] = true;
				if (get<0>(cur) == destRow && get<1>(cur) == destCol) {
					count = get<2>(cur);
					break;
				}
				if (get<0>(cur) - 2 >= 0 && get<1>(cur) - 1 >= 0 && !visited[get<0>(cur) - 2][get<1>(cur) - 1]) {
					q.push(make_tuple(get<0>(cur) - 2, get<1>(cur) - 1, get<2>(cur) + 1));
				}
				if (get<0>(cur) - 2 >= 0 && get<1>(cur) + 1 < l && !visited[get<0>(cur) - 2][get<1>(cur) + 1]) {
					q.push(make_tuple(get<0>(cur) - 2, get<1>(cur) + 1, get<2>(cur) + 1));
				}
				if (get<0>(cur) - 1 >= 0 && get<1>(cur) - 2 >= 0 && !visited[get<0>(cur) - 1][get<1>(cur) - 2]) {
					q.push(make_tuple(get<0>(cur) - 1, get<1>(cur) - 2, get<2>(cur) + 1));
				}
				if (get<0>(cur) - 1 >= 0 && get<1>(cur) + 2  < l && !visited[get<0>(cur) - 1][get<1>(cur) + 2]) {
					q.push(make_tuple(get<0>(cur) - 1, get<1>(cur) + 2, get<2>(cur) + 1));
				}
				if (get<0>(cur) + 1 < l && get<1>(cur) - 2 >= 0 && !visited[get<0>(cur) + 1][get<1>(cur) - 2]) {
					q.push(make_tuple(get<0>(cur) + 1, get<1>(cur) - 2, get<2>(cur) + 1));
				}
				if (get<0>(cur) + 1 < l && get<1>(cur) + 2 < l && !visited[get<0>(cur) + 1][get<1>(cur) + 2]) {
					q.push(make_tuple(get<0>(cur) + 1, get<1>(cur) + 2, get<2>(cur) + 1));
				}
				if (get<0>(cur) + 2 < l && get<1>(cur) - 1 >= 0 && !visited[get<0>(cur) + 2][get<1>(cur) - 1]) {
					q.push(make_tuple(get<0>(cur) + 2, get<1>(cur) - 1, get<2>(cur) + 1));
				}
				if (get<0>(cur) + 2 < l&& get<1>(cur) + 1 < l && !visited[get<0>(cur) + 2][get<1>(cur) + 1]) {
					q.push(make_tuple(get<0>(cur) + 2, get<1>(cur) + 1, get<2>(cur) + 1));
				}
			}
		}
		cout << count << '\n';
	}
	return 0;
}