ZeroJudge A982: Maze Problem #1

You are given an N×N grid maze where "#" represents obstacles and "." represents paths.

You start from a position (2, 2), with the top-left corner being (1, 1), and your destination is (N-1, N-1).

Find the shortest path length, including the starting point and the endpoint.

Sample Inputs/Outputs

Sample Input(s)Sample Output(s)
The first line contains a positive integer N (N does not exceed 100).
Following are N lines with N columns, representing the maze composed of '#' and '.'.		An integer representing the length of the shortest path. If it's not possible to reach the destination, print "No solution!"
9
(See Below)		13

Input's Maze

#########
#.......#
#.#####.#
#.......#
##.#.####
#..#.#..#
#.##.##.#
#.......#
#########
ZeroJudge A982: Input Table

Thought Process

This problem may encounter TLE if using DFS, so we should only use BFS to traverse the maze. When there is no starting point, it means it's impossible to reach the destination, so output "No solution!".

When reaching the destination, we can directly output the current step count because the first one to reach will be the shortest distance.

It's important to note that we need a map to store the points we've already visited, so we don't walk to the same point again. Otherwise, an infinite loop may occur.

Sample Code－ZeroJudge A982: Maze Problem #1

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

vector<vector<char>>v;
int N, minn = 99999;

pair<int, int> axis (int y, int x)
{
    pair<int, int>tmp;
    tmp.first = y;
    tmp.second = x;
    return tmp;
}

void BFS(vector<pair<int, int>>start, int count, map<pair<int, int>, int>MAP)
{
    if (start.size() == 0)
    {
        cout << "No solution!\n";
        return;
    }
    vector<pair<int, int>>newStart;
    for (int i = 0; i<start.size(); i++)
    {
        int y = start[i].first, x = start[i].second;
        MAP[axis(y, x)]++;
        if (y == N-1 && x == N-1)
        {
            cout << count << "\n";
            return;
        }
        if (y-1 >= 0 && v[y-1][x] == '.' && MAP[axis(y-1, x)] == 0) newStart.push_back(axis(y-1, x));
        if (y+1 <= N && v[y+1][x] == '.' && MAP[axis(y+1, x)] == 0) newStart.push_back(axis(y+1, x));
        if (x-1 >= 0 && v[y][x-1] == '.' && MAP[axis(y, x-1)] == 0) newStart.push_back(axis(y, x-1));
        if (x+1 <= N && v[y][x+1] == '.' && MAP[axis(y, x+1)] == 0) newStart.push_back(axis(y, x+1));
    }
    BFS(newStart, count+1, MAP);
}

int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    cin >> N;
    for (int i = 0; i<N; i++)
    {
        vector<char>tmp;
        for (int j = 0; j<N; j++)
        {
            char a;
            cin >> a;
            tmp.push_back(a);
        }
        v.push_back(tmp);
    }
    N--;
    map<pair<int, int>, int>MAP;
    MAP[axis(1, 1)]++;
    vector<pair<int, int>>tmp;
    tmp.push_back(axis(1, 1));
    BFS(tmp, 1, MAP);
}

//ZeroJudge A982
//Dr. SeanXD
Tags

Related Posts

Comments