給你一個 N＊N 格的迷宮，迷宮中以「#」代表障礙物，以「.」代表路。
你固定在 (2, 2) 出發，最左上角是 (1, 1)，目的地是 (N-1, N-1)。
求包括起點和終點，最少路徑的長度。
範例測資
| 範例輸入 | 範例輸出 |
|---|---|
| 第一行有一個正整數 N (N 不超過 100) 接下來有 N 行 N 列，由「#」和「.」組成的迷宮 | 一個正整數，代表最短路徑的長度 如果不可能到達終點，則印出「No solution!」 |
| 9 (迷宮請見下表格) | 13 |
輸入迷宮表格
| # | # | # | # | # | # | # | # | # |
| # | . | . | . | . | . | . | . | # |
| # | . | # | # | # | # | # | . | # |
| # | . | . | . | . | . | . | . | # |
| # | # | . | # | . | # | # | # | # |
| # | . | . | # | . | # | . | . | # |
| # | . | # | # | . | # | # | . | # |
| # | . | . | . | . | . | . | . | # |
| # | # | # | # | # | # | # | # | # |
解題思路
本題如果使用DFS會有TLE的情況出現，所以只能使用BFS的方式走，當沒有起點時就代表無法走到終點輸出No solution!。
當走到終點時可以直接輸出目前的步數，因為先跑到的就會是最短距離。
需要注意的是需要有一個 Map 來存已經走過的點，不能重複走到同一個點不然會有無限迴圈的情況出現。
範例程式碼－ZeroJudge A982: 迷宮問題#1
#include <iostream>
#include <vector>
#include <map>
using namespace std;
vector<vector<char>>v;
int N, minn = 99999;
pair<int, int> axis (int y, int x)
{
pair<int, int>tmp;
tmp.first = y;
tmp.second = x;
return tmp;
}
void BFS(vector<pair<int, int>>start, int count, map<pair<int, int>, int>MAP)
{
if (start.size() == 0)
{
cout << "No solution!\n";
return;
}
vector<pair<int, int>>newStart;
for (int i = 0; i<start.size(); i++)
{
int y = start[i].first, x = start[i].second;
MAP[axis(y, x)]++;
if (y == N-1 && x == N-1)
{
cout << count << "\n";
return;
}
if (y-1 >= 0 && v[y-1][x] == '.' && MAP[axis(y-1, x)] == 0) newStart.push_back(axis(y-1, x));
if (y+1 <= N && v[y+1][x] == '.' && MAP[axis(y+1, x)] == 0) newStart.push_back(axis(y+1, x));
if (x-1 >= 0 && v[y][x-1] == '.' && MAP[axis(y, x-1)] == 0) newStart.push_back(axis(y, x-1));
if (x+1 <= N && v[y][x+1] == '.' && MAP[axis(y, x+1)] == 0) newStart.push_back(axis(y, x+1));
}
BFS(newStart, count+1, MAP);
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 0; i<N; i++)
{
vector<char>tmp;
for (int j = 0; j<N; j++)
{
char a;
cin >> a;
tmp.push_back(a);
}
v.push_back(tmp);
}
N--;
map<pair<int, int>, int>MAP;
MAP[axis(1, 1)]++;
vector<pair<int, int>>tmp;
tmp.push_back(axis(1, 1));
BFS(tmp, 1, MAP);
}
//ZeroJudge A982
//Dr. SeanXD