Question Name:Shortest Source to Destination Path

#include<bits/stdc++.h>
using namespace std;
int n,m;
void s_to_d(int s_x,int s_y, int d_x,int d_y,int steps,int *min_step,int mat[30][30] )
{
//	cout<<"hii";
	if(s_x<0 || s_x >=n || s_y<0 || s_y >=m )
    return;
    else if(mat[s_x][s_y]==0)
    return;
    else
    if(s_x==d_x && s_y ==d_y)
    {
        if(*min_step>steps)
        {
            *min_step=steps;
        }
        return;
    }
    mat[s_x][s_y]=0;
    s_to_d(s_x-1,s_y,d_x,d_y,steps+1,min_step,mat);
    s_to_d(s_x+1,s_y,d_x,d_y,steps+1,min_step,mat);
    s_to_d(s_x,s_y-1,d_x,d_y,steps+1,min_step,mat);
    s_to_d(s_x,s_y+1,d_x,d_y,steps+1,min_step,mat);
   
    return;
}
int main()
 {
	int t,d_x,d_y;
	int mat [30][30];
	cin>>t;
	while(t--)
	{
	    cin>>n>>m;
	    for(int i=0;i<n;i++)
	    {
	        for(int j=0;j<m;j++)
	        {
	            cin>>mat[i][j];
	        }
	    }
	    cin>>d_x>>d_y;
	    int steps=0,min_step;
	    min_step=10000;
	    s_to_d(0,0,d_x,d_y,steps,&min_step,mat);
	    
	    if(min_step==10000)
	    cout<<"-1\n";
	    else
	    cout<<min_step<<"\n";
	}
	return 0;
}
  • Problem Description
    Given a boolean 2D matrix (0-based index), find whether there is path from (0,0) to (x,y) and if there is one path, print the minimum no of steps needed to reach it, else print -1 if the destination is not reachable.

    Input:

    The first line of input contains an integer T denoting the no of test cases. Then T test cases follow. Each test case contains two lines . The first line of each test case contains two integers n and m denoting the size of the matrix. 

    Then in the next line are n*m space separated values of the matrix. The following line after it contains two integers x and y denoting the index of the destination.

    Output:
    For each test case print in a new line the min no of steps needed to reach the destination.

    Constraints:
    1<=T<=100
    1<=n,m<=20
  • Test Case 1
    Input (stdin)2
    3 4
    1 0 0 0 1 1 0 1 0 1 1 1
    2 3
    3 4
    1 1 1 1 0 0 0 1 0 0 0 1
    0 3
    Expected Output5
    3
  • Test Case 2
    Input (stdin)1
    3 6
    1 0 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1
    0 5
    Expected Output-1

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.