ZeroJudge F671: 最短路徑

「無題目內容」

範例測資

範例輸入範例輸出
第 1 行給定兩個整數 N 和 M (1 <= N, M <= 10) 表示為一個表示為一個 N＊M 的網格，第 2 到 N+1 行每行有 M 個字元，字元可為「.」(代表路) 或「#」(代表障礙)，在路上可以上下左右的走，但不能超出邊界。輸出從左上角 (1, 1) 走到右下角 (N, M) 最少需要花多少步，如果走不到，請輸出 -1。
3 5
(請見下方表格)		10
ZeroJudge F671 範例測資

範例輸入

.#...
.#.#.
...#.

解題思路

可以設定一個為 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
標籤

相關文章

發佈留言