「無題目內容」
範例測資
範例輸入 | 範例輸出 |
---|---|
第 1 行給定兩個整數 N 和 M (1 <= N, M <= 10) 表示為一個表示為一個 N*M 的網格,第 2 到 N+1 行每行有 M 個字元,字元可為「.」(代表路) 或「#」(代表障礙),在路上可以上下左右的走,但不能超出邊界。 | 輸出從左上角 (1, 1) 走到右下角 (N, M) 最少需要花多少步,如果走不到,請輸出 -1。 |
3 5 (請見下方表格) | 10 |
範例輸入
. | # | . | . | . |
. | # | . | # | . |
. | . | . | # | . |
解題思路
可以設定一個為 99999 的變數用來比較最短距離,並且使用 BFS 的方式進行最短距離的判斷,如果跑完 BFS 之後變數還是 99999 代表無法走到這個點則輸出 -1。
範例程式碼-ZeroJudge F671: 最短路徑
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int N, M, ans = 99999;
vector<string>v;
map<pair<int, int>, int>MAP;
pair<int, int> axis (int a, int b)
{
pair<int, int>tmp;
tmp.first = a;
tmp.second = b;
return tmp;
}
void BFS(vector<pair<int, int>>start, int count)
{
if (start.size() == 0) return;
vector<pair<int, int>>newStart;
count++;
for (int i = 0; i<start.size(); i++)
{
int x = start[i].second, y = start[i].first;
MAP[axis(y, x)]++;
if (y == N-1 && x == M-1)
{
if (count < ans) ans = count;
return;
}
if (y + 1 < N && MAP[axis(y+1, x)] == 0 && v[y+1][x] != '#') newStart.push_back(axis(y+1, x));
if (y - 1 >= 0 && MAP[axis(y-1, x)] == 0 && v[y-1][x] != '#') newStart.push_back(axis(y-1, x));
if (x + 1 < M && MAP[axis(y, x+1)] == 0 && v[y][x+1] != '#') newStart.push_back(axis(y, x+1));
if (x - 1 >= 0 && MAP[axis(y, x-1)] == 0 && v[y][x-1] != '#') newStart.push_back(axis(y, x-1));
}
BFS(newStart, count);
}
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cin >> N >> M;
for (int i = 0; i<N; i++)
{
string str;
cin >> str;
v.push_back(str);
}
vector<pair<int, int>>tmp;
tmp.push_back(axis(0, 0));
BFS(tmp, 0);
if (ans == 99999) cout << -1 << "\n";
else cout << ans-1 << "\n";
}
//ZeroJudge F671
//Dr. SeanXD