Atcoder解いてみた AtCoder Beginner Contest E - Bishop 2

AtCoder Beginner Contest E - Bishop 2

問題はこちら

最初の回答

進む方向が同じであれば、いくつの辺を通ってもコストは0
元々、通常のBFSを使って、1つ前の方向と同じ方向をいくならコスト0、方向0ならコスト1として、ゴールまでたどり着いた時のコストを求める処理を書いた
しかし、以下の問題でWA

• 同じx,y座標にたどり着いても、どの方向からたどり着くかによって、次のコストのかかり方が変わる
• たどり着いているか否かの判定を行っているが、今回、木じゃないため、最短距離を求めるにあたり、今回のコードでは不十分

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>

int N;
int Ax, Ay;
int Bx, By;
std::vector<std::string> S;
std::vector<std::vector<long long>> dist;

int diff[4][2] = { {1,1},{1,-1},{-1,1},{-1,-1} };

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N;
	std::cin >> Ax >> Ay;
	std::cin >> Bx >> By;
	Ax--;
	Ay--;
	Bx--;
	By--;

	dist.resize(N);
	for (int i = 0; i < N; i++) {
		std::string s;
		std::cin >> s;
		S.push_back(s);
		dist[i].resize(N, -1);
	}

	// BFS 以前に進んだ方向も持つ
	std::queue<std::tuple<int, int, int>> q;
	dist[Ax][Ay] = 0;
	q.push({ Ax , Ay, -1 }); // 最初、方向は-1

	int ans = -1;

	while (!q.empty()) {
		auto [ux, uy, ud] = q.front();
		q.pop();

		// 隣接点
		for (int d = 0; d < 4; d++) {
			int vx = ux + diff[d][0];
			int vy = uy + diff[d][1];
			int vd = d;

			// はみ出さない
			if (vx < 0 || vx >= N || vy < 0 || vy >= N) {
				continue;
			}

			// 行く先がポーン
			if (S[vx][vy] == '#') {
				continue;
			}

			// すでに訪問されている
			if (dist[vx][vy] != -1) {
				continue;
			}

			// u→vへ訪問

			// 方向が違う場合、コスト+1
			if (ud != vd) {
				dist[vx][vy] = dist[ux][uy] + 1;
			}
			// 方向が同じ場合、コストかからない
			else {
				dist[vx][vy] = dist[ux][uy];
			}

			// ゴール
			if (vx == Bx && vy == By){
				ans = dist[vx][vy];
			}

			q.push({ vx, vy, vd });
		}
	}

	std::cout << ans << std::endl;


	return 0;
}

解説の回答

• x,y座標の情報のみならず、方向の情報も持った
• 最短距離(今回の場合は、最短手数)を更新できるようにした
• コストが0,1のBFSにはコツが必要で、コスト0から消費できるようにdequeを使っている

※1手目は必ずコストがかかるため、処理を分けている

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <limits.h>
#include <bitset>
#include <list>
#include <set>
#include <numeric>
#include <tuple>

int N;
int Ax, Ay;
int Bx, By;
std::vector<std::string> S;

int diff[4][2] = { {1,1},{1,-1},{-1,1},{-1,-1} };

int main()
{
	std::cin.tie(0);
	std::ios::sync_with_stdio(false);

	std::cin >> N;
	std::cin >> Ax >> Ay;
	std::cin >> Bx >> By;
	Ax--;
	Ay--;
	Bx--;
	By--;

	std::vector<std::vector<std::vector<int>>> dist(N, std::vector<std::vector<int>>(N, std::vector<int>(4, -1)));

	for (int i = 0; i < N; i++) {
		std::string s;
		std::cin >> s;
		S.push_back(s);
	}

	// BFS 以前に進んだ方向も持つ
	std::deque<std::tuple<int, int, int>> dq;
	dist[Ax][Ay][0] = 0;
	dist[Ax][Ay][1] = 0;
	dist[Ax][Ay][2] = 0;
	dist[Ax][Ay][3] = 0;
	dq.push_back({ Ax , Ay, -1 }); // 最初、方向は-1

	// 最初の一手を行い、全方向の点をキューに入れる
	auto [ux, uy, ud] = dq.front();
	dq.pop_front();

	// 隣接点
	for (int d = 0; d < 4; d++) {
		int vx = ux + diff[d][0];
		int vy = uy + diff[d][1];
		int vd = d;

		// はみ出さない
		if (vx < 0 || vx >= N || vy < 0 || vy >= N) {
			continue;
		}

		// 行く先がポーン
		if (S[vx][vy] == '#') {
			continue;
		}

		// u→vへ訪問
		// 最初は必ずコストがかかる
		dist[vx][vy][d] = dist[ux][uy][d] + 1;
		dq.push_back({ vx, vy, vd });
	}

	

	while (!dq.empty()) {
		auto [ux, uy, ud] = dq.front();
		dq.pop_front();

		// 隣接点
		for (int d = 0; d < 4; d++) {
			int vx = ux + diff[d][0];
			int vy = uy + diff[d][1];
			int vd = d;

			// はみ出さない
			if (vx < 0 || vx >= N || vy < 0 || vy >= N) {
				continue;
			}

			// 行く先がポーン
			if (S[vx][vy] == '#') {
				continue;
			}

			// u→vへ訪問

			// 同じ点、同じ方向でも異なる経路から到達しうることを考慮する必要がある
			// 到達コストの小さい順で優先して処理するため、コストがかからない場合、queの前に、
			// コストがかかる場合、queの後にデータを入れる

			// 方向が違う場合、コスト+1
			int newDist;
			if (ud != vd) {
				newDist = dist[ux][uy][ud] + 1;
			}
			// 方向が同じ場合、コストかからない
			else {
				newDist = dist[ux][uy][ud];
			}

			// すでに訪問されているかつ、最短距離が見つからない
			if (dist[vx][vy][vd] != -1 && newDist >= dist[vx][vy][vd]) {
				continue;
			}
			dist[vx][vy][vd] = newDist;

			if (ud != vd) {
				dq.push_back({ vx, vy, vd });
			}
			// 方向が同じ場合、コストかからない
			else {
				dq.push_front({ vx, vy, vd });
			}
		}
	}

	// BFSが人と落ち終わってから
	int ans = INT_MAX;
	for (int d = 0; d < 4; d++) {
		if (dist[Bx][By][d] != -1) {
			ans = std::min(dist[Bx][By][d], ans);
		}
	}

	if (ans == INT_MAX) {
		std::cout << -1 << std::endl;
	}
	else {
		std::cout << ans << std::endl;
	}


	return 0;
}