[BFS] 데스 나이트

예제 입력 1

7

6 6 0 1

예제 출력 1

4

예제 입력 2

6

5 1 0 5

예제 출력 2

-1

예제 입력 3

7

0 3 4 3

예제 출력 3

2

 

 

 

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

16948번: 데스 나이트

#include <stdio.h>

const int MAX_QUEUE_SIZE = 2000;
const int MAX_SIZE = 201;
const int DIRECTION_COUNT = 6;

int dist[MAX_SIZE][MAX_SIZE] = { 0, };

int dR[DIRECTION_COUNT] = { -2, -2, 0, 0, 2, 2 };
int dC[DIRECTION_COUNT] = { -1, 1, -2, 2, -1, 1 };

class Pair
{
public:
	int r;
	int c;

	Pair() { r = c = 0; }

	bool isInBoundary(int N)
	{
		return (r >= 0 && r < N && c >= 0 && c < N);
	}

	bool operator==(Pair other)
	{
		return (r == other.r) && (c == other.c);
	}
};

template <typename T>
class Queue
{
public:
	int front;
	int rear;

	T item[MAX_QUEUE_SIZE];

	Queue()
	{
		front = rear = 0;
	}

	void push(T _item)
	{
		item[rear] = _item;
		rear = (rear + 1) % MAX_QUEUE_SIZE;
	}

	T pop()
	{
		T result = item[front];
		front = (front + 1) % MAX_QUEUE_SIZE;

		return result;
	}

	bool isEmpty() { return front == rear; }
};
Queue<Pair> q;
Pair now;
Pair target;

int N;

int main(void)
{
	scanf("%d", &N);
	scanf("%d %d %d %d", &now.r, &now.c, &target.r, &target.c);

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			dist[i][j] = -1;
		}
	}

	q.push(now);
	dist[now.r][now.c] = 0;

	while (!q.isEmpty())
	{
		Pair now = q.pop();

		if (now == target)
		{
			printf("%d\n", dist[now.r][now.c]);
			return 0;
		}

		for (int i = 0; i < DIRECTION_COUNT; i++)
		{
			Pair next;
			next.r = now.r + dR[i];
			next.c = now.c + dC[i];

			if (!next.isInBoundary(N)) continue;

			if (dist[next.r][next.c] == -1)
			{
				q.push(next);
				dist[next.r][next.c] = dist[now.r][now.c] + 1;
			}
		}
	}

	printf("-1\n");
	return 0;
}