#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