ZeroJudge D821: 最短路徑個數

地圖上，由 (Sx, Sy) 只能上下左右到達 (Ex, Ey) 的最短路徑長

想必大家都已經不陌生了，那麼現在請寫出

(Sx, Sy) → (Ex, Ey) 的最短路徑個數

範例測資

範例輸入範例輸出
EOF 輸入，每組測資第一行有兩個整數 N 和 M (1 ≦ N, M ≦ 50)
接下來會有 N 行
每行上分別有 M 個 0 和 1 構成的地圖
0 代表可以通行，1 代表有障礙物
接下來還會有一行有四個數字：Sx、Sy、Ex、Ey
0 ≦ Sx, Ex < N，0 ≦ Sy, Ey < M
左上角為 (0, 0)，右下角為 (N-1, M-1)		答案可能很大，請輸出 Mod 100000 後的結果
5 5
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 4 4
6 5
0 0 0 0 0
0 1 0 1 0
0 1 1 1 0
0 0 1 1 0
0 1 1 0 0
0 0 0 0 0
0 4 5 0
6 5
0 0 0 0 0
0 1 0 1 0
0 1 0 1 0
0 0 0 1 0
0 1 0 0 0
0 0 0 0 0
0 4 5 0		70
3
6
ZeroJudge D821 範例測資

解題思路

先預設一個 N＊M 的二維陣列並且將裡面的資料預設為 0，並且將起點位置的值變成 1。和普通的 BFS 差不多，只是在每次判斷可以往某個方向走的時候要在新的點上加上原先目前的點中的值。另外，最後 4 個數字是 y, x, y, x，而不是 x, y, x, y，這點需注意。

範例程式碼－ZeroJudge D821: 最短路徑個數

#include <iostream>
#include <vector>
#include <map>
using namespace std;

int N, M;
vector<vector<int>>v;
vector<vector<long long int>>value;
pair<int, int>start, finish;
map<pair<int, int>, int>MAP;
int loc[4][2] = {{0,-1} , {-1,0} , {1,0} , {0,1}};

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>>begin)
{
    if (begin.size() == 0) return;
    vector<pair<int, int>>newStart;
    for (int i = 0; i<begin.size(); i++)
    {
        int x = begin[i].second, y = begin[i].first;
        if (x == finish.second && y == finish.first) return;
        if (MAP[begin[i]] != 0) continue;
        MAP[begin[i]]++;
        for (int j = 0; j<4; j++)
        {
            int xx = x + loc[j][0], yy = y + loc[j][1];
            if (xx >= 0 && xx < M && yy >= 0 && yy < N && MAP[axis(yy, xx)] == 0 && v[yy][xx] == 0)
            {
                newStart.push_back(axis(yy, xx));
                value[yy][xx] = (value[y][x] + value[yy][xx]) % 100000;
            }
        }
    }
    BFS(newStart);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    while (cin >> N >> M)
    {
        v.clear();
        value.clear();
        for (int i = 0; i<N; i++)
        {
            vector<int>hi;
            vector<long long int>zero;
            for (int j = 0; j<M; j++)
            {
                int tmp;
                cin >> tmp;
                hi.push_back(tmp);
                zero.push_back(0);
                MAP[axis(i, j)] = 0;
            }
            value.push_back(zero);
            v.push_back(hi);
        }
        int x, y;
        cin >> y >> x;
        start.second = x;
        start.first = y;
        cin >> y >> x;
        finish.second = x;
        finish.first = y;
        vector<pair<int, int>>tmp;
        tmp.push_back(start);
        value[start.first][start.second] = 1;
        BFS(tmp);
        cout << value[finish.first][finish.second] << "\n";
    }
}

//ZeroJudge D821
//Dr. SeanXD
標籤

相關文章

發佈留言