白駿16948号の死の夜.



質問リンク

コードの説明


これは基本的なBFS探索法である.地図上で直接カウントする方法.
その後目的地に到着した場合、breakを停止してカウントを出力します.

ソースコード

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

int dx[] = { -2,-2,0,0,2,2 };
int dy[] = { -1,1,-2,2,-1,1 };
int N;
int map[201][201];
bool visited[201][201];
int target[4];
int cnt;
void bfs(int y, int x) {
	queue<pair<int, int>> q;
	q.push({ y,x });
	visited[y][x] = true;

	while (!q.empty()) {
		int y = q.front().first;
		int x = q.front().second;
		q.pop();
		for (int i = 0; i < 6; i++) {
			int ny = y + dy[i];
			int nx = x + dx[i];
			if (ny < 0 || ny >= N || nx < 0 || nx >= N) continue;
			if (!visited[ny][nx]) {
				visited[ny][nx] = true;
				map[ny][nx] = map[y][x] + 1;
				q.push({ ny,nx });
			}

			if (ny == target[3] && nx == target[2]) {
				cnt = map[ny][nx];
			}

		}
	}
	if (cnt == 0) cnt = -1;
}

int main() {
	cin >> N;
	for (int i = 0; i < 4; i++) {
		cin >> target[i];
	}
	bfs(target[1], target[0]);

	cout << cnt;
	return 0;
}