ZeroJudge F671: Shortest Route

No Content:(

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line provides two integers, N and M (1 ≤ N, M ≤ 10), representing an N×M grid. The following N lines (from the 2nd to N+1th lines) each contain M characters. Each character can be either '.' (representing a path) or '#' (representing an obstacle). On the path, movement is allowed in all four directions (up, down, left, right), but it cannot exceed the boundaries.Output the minimum number of steps required to walk from the top-left corner (1, 1) to the bottom-right corner (N, M). If it's not possible to reach the destination, output -1.
3 5
(Please see the chart below)		10
ZeroJudge F671 Sample Input/Output

Sample Input(s)

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

Thought Process

You can set a variable to 99999 for comparing the shortest distance and use the BFS (Breadth-First Search) algorithm to determine the shortest distance. If the variable remains 99999 after running BFS, it indicates that it's not possible to reach that point, so output -1.

Sample Code－ZeroJudge F671: Shortest Route

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

Related Posts

Comments