# Untitled

unknown
plain_text
3 years ago
2.4 kB
1
Indexable
Never
```// Initial Template for C++

#include <bits/stdc++.h>
using namespace std;

// } Driver Code Ends
// User function Template for C++

class Solution {
public:
int shortestDistance(int N, int M, vector<vector<int>> A, int X, int Y) {
// code here
map<int,vector<int>>mp;
int k=0,src = 0,dest;
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(i==X and j==Y){
dest = k;
}
//checking all 4 sides of a node
if(A[i][j]!=0){
if(i-1>-1 and A[i-1][j]!=0){
mp[k].push_back(k-M);
}
if(i+1<N and A[i+1][j]!=0){
mp[k].push_back(k+M);
}
if(j-1>-1 and A[i][j-1]!=0){
mp[k].push_back(k-1);
}
if(j+1<M and A[i][j+1]!=0){
mp[k].push_back(k+1);
}
}
k++;
}
}
// for(auto x:mp){
//     cout<<x.first<<":";
//     vector<int> v = x.second;
//     for(auto y:v){
//         cout<<y<<" ";
//     }cout<<endl;
// }

//BFS traversal for shortest path
queue<pair<int,int>> q; //node vale,level
q.push(make_pair(src,0));
pair<int,int> node;
vector<bool> visited(N*M);
visited[src] = true;
while(!q.empty()){
node = q.front();
if(node.first==dest){
return node.second;
}
q.pop();
vector<int> v = mp[node.first];
for(int i=0;i<v.size();i++){
if(visited[v[i]]!=true){
q.push({v[i],node.second+1});
visited[v[i]] = true;
}
}
}
return -1;
}
};

// { Driver Code Starts.
int main() {
int t;
cin >> t;
while (t--) {
int N, M, x, y;
cin >> N >> M;
vector<vector<int>> v(N, vector<int>(M));
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++) cin >> v[i][j];
cin >> x >> y;
Solution ob;
cout << ob.shortestDistance(N, M, v, x, y) << "\n";
}
}  // } Driver Code Ends```