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

나이트가 a, b에서 x, y까지 가는데 걸리는 최소 이동횟수를 구하는 문제입니다.

나이트의 이동을 배열로 선언했습니다.
int moveX[8] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int moveY[8] = { 1, -1, 1, -1, 2, -2, 2, -2 };

BFS를 통해서 모든 경로를 찾고 x, y에 도착하면
이동횟수를 출력했습니다.

 

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

int moveX[8] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int moveY[8] = { 1, -1, 1, -1, 2, -2, 2, -2 };

int main(int argc, char* argv[])
{
	int ts;
	int n;
	int a, b, c;
	int x, y;
	int findA, findB;
	int flag = 0;
	int map[310][310];
	queue<pair<pair<int, int>, int > >q;

	cin >> ts;

	while (ts--) {
		flag = 0;

		cin >> n;
		cin >> a >> b;
		cin >> findA >> findB;

		memset(map, 0, sizeof(map));
		while (!q.empty()) {
			q.pop();
		}

		q.push(make_pair(make_pair(a, b), 0));

		while (1) {
			a = q.front().first.first;
			b = q.front().first.second;
			c = q.front().second;
			map[a][b] = 1;
			q.pop();

			if (a == findA && b == findB) {
				break;
			}

			for (int i = 0; i < 8; ++i) {
				x = moveX[i] + a;
				y = moveY[i] + b;
				if (x == findA && y == findB) {
					flag = 1;
					break;
				}
				if (x >= 0 && y >= 0 && x < n && y < n && !map[x][y]) {
					q.push(make_pair(make_pair(x, y), c + 1));
					map[x][y] = 1;
				}
				
			}
			if (flag) {
				++c;
				break;
			}
		}
		cout << c << endl;
	}

	return 0;
}