ZeroJudge D821: Number of Shortest Route

The shortest path length from (Sx, Sy) to (Ex, Ey) on the map, where movement is allowed only in the up, down, left, and right directions.

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

The number of shortest paths from (Sx, Sy) to (Ex, Ey) on the map.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
EOF inputs: each set of test data consists of two integers on the first line. N 和 M (1 ≦ N, M ≦ 50)
Following that, there will be N lines.
Each line contains a map composed of M characters, each character being either 0 or 1.
0 represents passable terrain, while 1 represents an obstacle.
Then, there will be another line containing four numbers: Sx, Sy, Ex, Ey.
0 ≦ Sx, Ex < N，0 ≦ Sy, Ey < M
The top-left corner is represented as (0, 0), and the bottom-right corner is represented as (N-1, M-1).		Output the result modulo 100000, as the answer may be large.
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 範例測資

Thought Process

First, initialize an N×M 2D array and set all elements to 0, then set the value at the starting point to 1. The process is similar to regular BFS, but whenever it's possible to move in a certain direction, add the value from the current point to the new point. Additionally, note that the last four numbers are y, x, y, x, not x, y, x, y.

Sample Code－ZeroJudge D821: Number of Shortest Route

#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
Tags

Related Posts

Comments