The Easy Solution - Graph Theory

Wondered about how to find a solution to the maze in the shortest path and the shortest time.
Here is the solution :-

Let the Computer do it with these few lines of C code and a little bit of an application of graph theory

So the algorithm is pretty simple , just check which directions can you take step in currently , take that step and increase the answer by one , then go to all the ends of the paths , and increase the path length in all directions possible by one and after traversing all ends , again increase the answer by one .
Repeat the procedure till you reach the end , There you have the answer of the number of steps requried to reach the end in minimum steps and time . You can modify the code a bit to incorporate the storage of the best path too.

Here is the question and its link on codechef.com

https://www.codechef.com/problems/DAY4P2

Problem

You are inside an NxM maze which you have to exit. Also, let us name this maze “IIIT D” and
the exit “graduation”.
You have to calculate, given a maze, the minimum number of steps you need to take from the
starting point to reach the exit. If the exit is unreachable from the starting point, print ­1

Input

First line contains 2 integers : N and M.

Each of the next N lines contain M characters, “.” denoting blank space, “#” denoting wall, “S”
denoting your starting position and “E” denoting exit. You are at S and have to move to E
through a sequence of moves. Legal moves are defined below.

If you are at some cell, you can move to any of the 4 adjacent cells that are not walls. e.g.

.##

S..

#..


In the above (incomplete) maze, you can only move upwards and rightwards as the cell
directly below you is occupied by a wall.

Sample Input:

4 5

#....

..#.#

E#...

#S.#.

Output

On a single line, output the number of minimum steps to reach exit, or “­-1” if this is not
possible.

Sample Output:

10

Constraints

1<=N<=10^3

1<=M<=10^3 

Explanation

One can reach from S to E by the moves : right, up, right, up, up, left, left, down, left, down

Here is the C code for you :-

#include <iostream>
#include<queue>
using namespace std;


int n,m,ans=0,sr,sc,r,c;
queue <int> rq,cq;
char grid[1000][1000];

bool visited[1000][1000]={0};
int nodes_left_in_layer=1;
int nodes_in_next_layer=0;

int dr[4]={1,-1,0,0};
int dc[4]={0,0,1,-1};


void explore_neighbours(int r,int c)
{
    int rr,rc;
    for(int i=0;i<4;i++)
    {
        rr=r+dr[i];
        rc=c+dc[i];
        if(rr>=n || rc>=m)
        {
            continue;
        }
        if(rr<0 || rc<0)
        {
            continue;
        }
        if(visited[rr][rc]==true || grid[rr][rc]=='#')
        {
            continue;
        }
        visited[rr][rc]=true;
        rq.push(rr);
        cq.push(rc);
        nodes_in_next_layer++;
       
    }
}


int solve()
{
 while(rq.size()>0)
 {
     r=rq.front();
     c=cq.front();
     rq.pop();
     cq.pop();
     if(grid[r][c]=='E')
     {
         return ans;
         break;
     }
     else
     {
         explore_neighbours(r,c);
         nodes_left_in_layer--;
         if(nodes_left_in_layer==0)
         {
             nodes_left_in_layer=nodes_in_next_layer;
             nodes_in_next_layer=0;
             ans++;
         }
     }
 }
   
   
 return -1; 
   
}



int main() {
    cin>>n>>m;
    int i=0,j=0;
    char c;
    while(i!=n)
    {
        j=0;
        while(j!=m)
        {
            cin>>c;
            grid[i][j]=c;
            j++;
        }
        i++;
    }
    i=0;j=0;
    while(i!=n)
    {
        j=0;
        while(j!=m)
        {
            if(grid[i][j]=='S')
            {
              sr=i;
              sc=j;
            }
            j++;
        }
        i++;
    }
    rq.push(sr);
    cq.push(sc);
    visited[sr][sc]=1;
    int t=solve();
    cout<<t<<endl;
   
   
   
   
// your code goes here
return 0;
}