PKU 1915 Knight Moves

• 300x300なので幅優先探索で十分
• 広げる方向は8方向

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

int main() {
	int numberOfTests;
	cin >> numberOfTests;

	for (int testIndex = 0; testIndex < numberOfTests; ++testIndex) {
		int length, startX, startY, goalX, goalY;
		cin >> length >> startX >> startY >> goalX >> goalY;

		static int table[512][512];
		memset(table, 0, sizeof(table));

		deque<int> q;
		q.push_back(startX);
		q.push_back(startY);
		table[startX][startY] = 1;
		while (!q.empty()) {
			const int x = q.front();
			q.pop_front();
			const int y = q.front();
			q.pop_front();

			for (int dir = 0; dir < 8; ++dir) {
				const int nextX = x + dx[dir];
				const int nextY = y + dy[dir];

				if (nextX < 0 || nextY < 0 || length <= nextX || length <= nextY) {
					continue;
				}

				if (table[nextX][nextY]) {
					continue;
				}

				table[nextX][nextY] = table[x][y] + 1;
				q.push_back(nextX);
				q.push_back(nextY);
			}
		}

		cout << table[goalX][goalY] - 1 << endl;
	}
}