043.md

043 - Maze Challenge with Lack of Sleep (★4)

解答

#include <iostream>
#include <vector>
#include <string>
#include <deque>
#include <array>
#include <algorithm> // std::min_element()

constexpr int INF = 2'000'000'000;

struct Dir
{
	std::array<int, 4> costs = { INF, INF, INF, INF };
};

struct State
{
	int x, y;
	int dir; // top: 0, right: 1, down: 2, left: 3
};

int main()
{
	// 縦 H, 横 W
	int H, W;
	std::cin >> H >> W;

	// (cs, rs) から (ct, rt) に移動
	int rs, cs;
	std::cin >> rs >> cs;
	--rs; --cs;
	int rt, ct;
	std::cin >> rt >> ct;
	--rt; --ct;

	std::vector<std::string> S(H);
	for (int i = 0; i < H; ++i)
	{
		// 1 行分まとめて入力
		std::cin >> S[i];
	}

	std::vector<std::vector<Dir>> d(H, std::vector<Dir>(W));
	
	// 最初のマスのコストは 0
	d[rs][cs].costs.fill(0);

	// 幅優先探索
	// (01-BFS を使うので std::deque)
	std::deque<State> deq;

	for (int i = 0; i < 4; ++i)
	{
		deq.push_back({ cs, rs, i });
	}

	while (!deq.empty())
	{
		const State current = deq.front();
		deq.pop_front();

		// i は top: 0, right: 1, down: 2, left: 3
		for (int i = 0; i < 4; ++i)
		{
			constexpr int dx[4] = { 0, 1, 0, -1 };
			constexpr int dy[4] = { -1, 0, 1, 0 };

			// 次のマスの座標
			const int nx = (current.x + dx[i]);
			const int ny = (current.y + dy[i]);

			// 次のマスが範囲外の場合スキップ
			if ((nx < 0) || (W <= nx)
				|| (ny < 0) || (H <= ny))
			{
				continue;
			}

			// 次のマスが壁の場合スキップ
			if (S[ny][nx] == '#')
			{
				continue;
			}

			// 次のマスへのコスト
			int cost = d[current.y][current.x].costs[current.dir];
			
			// 現在の方向とは異なる方向への移動の場合
			if (current.dir != i)
			{
				// コストを増やす
				++cost;
			}

			// コストがこれまでの記録を下回る場合
			if (cost < d[ny][nx].costs[i])
			{
				// 更新
				d[ny][nx].costs[i] = cost;

				// 01-BFS
				if (current.dir == i)
				{
					deq.push_front({ nx, ny, i });
				}
				else
				{
					deq.push_back({ nx, ny, i });
				}
			}
		}
	}

	// ゴールのマス
	const auto& goal = d[rt][ct];

	// 最小のコストを取得
	const int answer = *std::min_element(goal.costs.begin(), goal.costs.end());

	// 解答を出力
	std::cout << answer << '\n';
}