【題解】Zerojudge a982 - 迷宮問題#1

題目連結

題目大意

給定一個迷宮，問從起點到終點的最短路徑，或輸出無解。

題解

我們使用 BFS 演算法來搜索從起點到終點的最短路徑。從起點開始，逐層擴展，直到找到終點。在這個過程中，我們需要維護一個隊列 std::queue 來存儲待處理的節點。將起點加入隊列中，並開始迭代。每次從隊列中取出最前面的節點，擴展其四個方向相鄰且合法 (可通行且未被訪問過) 的節點，更新最短路徑的距離並將它們加入 std::queue。其他實作的細節請參考 code。

#include <bits/stdc++.h>
using namespace std;

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<string> grid(n);
	for(int i = 0; i < n; i++) {
		cin >> grid[i];
	}
	const int INF = 1E9;
	vector<vector<int>> dist(n, vector<int>(n, INF));
	dist[1][1] = 1;
	queue<pair<int, int>> que;
	que.emplace(1, 1);
	while(!que.empty()) {
		auto [x, y] = que.front();
		que.pop();
		for(int dir = 0; dir < 4; dir++) {
			int nx = x + dx[dir];
			int ny = y + dy[dir];
			if(nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] != '#' && dist[nx][ny] > dist[x][y] + 1) {
				dist[nx][ny] = dist[x][y] + 1;
				que.emplace(nx, ny);
			}
		}
	}
	if(dist[n - 2][n - 2] == INF) {
		cout << "No solution!\n";
	} else {
		cout << dist[n - 2][n - 2] << "\n";
	}
	return 0;
}

如果本文對您有幫助的話幫忙點擊廣告和分享吧！

© 若無特別註明，本站文章皆由 WeakMouse's Coding Blog 原創 ，轉載引用本文前請先留言告知。本文轉載請註明文章源自 WeakMouse's Coding Blog ，作者 ，並附上原文連結： 【題解】Zerojudge a982 - 迷宮問題#1