Knights Move

문제 요약 : 체스 판의 크기와 출발점, 도착점이 주어지는데, 프로그래머는 출발점에서 시작하여 도착점으로 몇번 만에 도착하는가를 출력해야 합니다.

문제 링크

알고리즘 : BFS

자료구조 : 원형 큐(배열로 구현)

느낀 점 : STL의 deque... 엄청나게 느리다는 것.

Accept된 소스 코드

#include<iostream>

using namespace std;

typedef struct {
	int x, y;
}Point;

const int qSize = 90000;
Point q[qSize];
int pop = 0, push = 0;
int N, boardSize;
Point first, end, cur;
int board[300][300];
int curValue, childValue;
int left1, left2, right1, right2, up1, up2, down1, down2;

void init() {
	for(int i = 0; i < 300; i++) {
		for(int j = 0; j < 300; j++) {
			board[i][j] = -1;
		}
	}
	pop = 0;
	push = 0;
}

int BFS() {
	while(pop != push) {
		cur.x = q[pop].x;
		cur.y = q[pop].y;
		pop = (pop + 1) % qSize;
		curValue = board[cur.x][cur.y];
		childValue = curValue + 1;

		if(cur.x == end.x && cur.y == end.y) return curValue;

		left1 = cur.x - 1;
		left2 = cur.x - 2;
		right1 = cur.x + 1;
		right2 = cur.x + 2;
		up1 = cur.y - 1;
		up2 = cur.y - 2;
		down1 = cur.y + 1;
		down2 = cur.y + 2;

		if(left1 >= 0 && left1 < boardSize) {
			if(up2 >= 0 && up2 < boardSize) {
				if(board[left1][up2] == -1) {
					q[push].x = left1;
					q[push].y = up2;
					push = (push + 1) % qSize;
					board[left1][up2] = childValue;
				}
			}
			if(down2 >= 0 && down2 < boardSize) {
				if(board[left1][down2] == -1) {
					q[push].x = left1;
					q[push].y = down2;
					push = (push + 1) % qSize;
					board[left1][down2] = childValue;
				}
			}
		}

		if(left2 >= 0 && left2 < boardSize) {
			if(up1 >= 0 && up1 < boardSize) {
				if(board[left2][up1] == -1) {
					q[push].x = left2;
					q[push].y = up1;
					push = (push + 1) % qSize;
					board[left2][up1] = childValue;
				}
			}
			if(down1 >= 0 && down1 < boardSize) {
				if(board[left2][down1] == -1) {
					q[push].x = left2;
					q[push].y = down1;
					push = (push + 1) % qSize;
					board[left2][down1] = childValue;
				}
			}
		}

		if(right1 >= 0 && right1 < boardSize) {
			if(up2 >= 0 && up2 < boardSize) {
				if(board[right1][up2] == -1) {
					q[push].x = right1;
					q[push].y = up2;
					push = (push + 1) % qSize;
					board[right1][up2] = childValue;
				}
			}
			if(down2 >= 0 && down2 < boardSize) {
				if(board[right1][down2] == -1) {
					q[push].x = right1;
					q[push].y = down2;
					push = (push + 1) % qSize;
					board[right1][down2] = childValue;
				}
			}
		}

		if(right2 >= 0 && right2 < boardSize) {
			if(up1 >= 0 && up1 < boardSize) {
				if(board[right2][up1] == -1) {
					q[push].x = right2;
					q[push].y = up1;
					push = (push + 1) % qSize;
					board[right2][up1] = childValue;
				}
			}
			if(down1 >= 0 && down1 < boardSize) {
				if(board[right2][down1] == -1) {
					q[push].x = right2;
					q[push].y = down1;
					push = (push + 1) % qSize;
					board[right2][down1] = childValue;
				}
			}
		}

	}
}

int main() {
	//freopen("input.txt", "r", stdin);

	cin >> N;
	while(N--) {
		cin >> boardSize;
		cin >> first.x >> first.y;
		cin >> end.x >> end.y;

		init();

		board[first.x][first.y] = 0;
		q[push].x = first.x;
		q[push].y = first.y;
		push = (push + 1) % qSize;

		cout << BFS() << endl;
	}


	return 0;
}