CODEWITHSUNDEEP
algorithmgraph
K.Smith
K.Smith

Reputation: 13

Find the shortest path to the end for multiple starting locations

There is a maze with size N by M, which has walls and corridors. There is gold somewhere in the maze and there are some people in the maze as well. The task is to find what the shortest path from some person to the prize is, as well as which person is going to get the prize.

I know how to solve it if there was only one person, but not if there are more than one.

The input is as follows. On the first line N, M and Q (the number of people are inputted). The on N lines M characters are inputted (. for corridor and # for wall). And then on Q lines the coordinates of each person are inputted.

If some person can get to the gold, the program should output the length of the shortest path and which person gets to it (if more than one get to it at the same time any single one of them is a correct output). And if there is no path the program should output -1.

Upvotes: 1

Views: 341

Answers (1)

indjev99
indjev99

Reputation: 134

The easiest way to solve this is to start from the gold and find the shortest path to any person, using BFS (Breadth First Search). Here is my implementation:

#include<iostream>
#include<queue>
using namespace std;
const int MAX_N=100; //you didn't say the restrictions so I am going to leave it as a 100
int n,m,q;
char maze[MAX_N][MAX_N];
vector<pair<int,int> > p;
int len[MAX_N][MAX_N]; //stores if we have visited the node and the length to there
int main()
{
    cin>>n>>m>>q;
    for (int i=0;i<n;++i)
    {
        for (int j=0;j<m;++j)
        {
            cin>>maze[i][j];
            len[i][j]=-1;
        }
    }
    int x,y;
    for (int i=0;i<q;++i)
    {
        cin>>x>>y;
        --y;
        --x;
        p.push_back(make_pair(y,x));
        maze[y][x]='p';
    }
    /*
    You didn't say when we input the gold's coordinates, so I'm going to assume it is in the end.
    */
    cin>>x>>y;
    --y;
    --x;
    len[y][x]=0;
    queue<pair<int,int> > qu;
    qu.push(make_pair(y,x));
    while (!qu.empty())
    {
        y=qu.front().first;
        x=qu.front().second;
        qu.pop();
        if (maze[y][x]=='p')
        {
            //we have reached a person and just need to find which it is
            for (int i=0;i<q;++i)
            {
                if (p[i].first==y && p[i].second==x)
                {
                    cout<<len[y][x]<<" "<<i+1<<endl;
                    return 0;
                }
            }
        }
        if (y>0 && maze[y-1][x]!='#' && len[y-1][x]==-1)
        {
            len[y-1][x]=len[y][x]+1;
            qu.push(make_pair(y-1,x));
        }
        if (y<n-1 && maze[y+1][x]!='#' && len[y+1][x]==-1)
        {
            len[y+1][x]=len[y][x]+1;
            qu.push(make_pair(y+1,x));
        }
        if (x>0 && maze[y][x-1]!='#' && len[y][x-1]==-1)
        {
            len[y][x-1]=len[y][x]+1;
            qu.push(make_pair(y,x-1));
        }
        if (x<m-1 && maze[y][x+1]!='#' && len[y][x+1]==-1)
        {
            len[y][x+1]=len[y][x]+1;
            qu.push(make_pair(y,x+1));
        }
    }
    cout<<-1<<endl;
    return 0;
}

Upvotes: 1

Related Questions