ZeroJudge F671: 最短路徑

題目敘述

每筆測資第一行有兩個正整數N和M，接下來要收N行字串，每個字串分別有M個字元。如果是 '.' 的話代表是可以走的路，如果是 '#' 的話代表是路障。要求輸出從 (0, 0) 也就是最左上角的點走到最右下角的點的最短距離為何，如果無法走到的話則輸出-1。

範例輸入 #1

3 5

.#...

.#.#.

...#.

範例輸出 #1

10

解題思路

可以設定一個為99999的變數用來比較最短距離，並且使用BFS的方式進行最短距離的判斷，如果跑完BFS之後變數還是99999代表無法走到這個點則輸出-1。

解題程式碼如下 (僅供參考)：

#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";
}