ZeroJudge D821: 最短路徑個數

題目敘述

本題採EOF方式收資料，每筆測資第一行有兩個正整數N和M，接下來要收一個N*M的數字陣列，0代表可以走的路，1代表是路障不能走。最後會有4個整數代表起點和終點。要求輸出從起點到終點的最短路徑個數。

範例輸入 #1

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

範例輸出 #1

70

3

6

解題思路

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

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

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