Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- // #Graph #BFS
- // given a maze and source and destination return min steps reqd
- vector<vector<int> > grid; // global
- bool valid(int x,int y){
- // [0,n-1] for 0 indexed
- if(x<0 || y<0 || x>=grid.size() || y>=grid[0].size() || grid[x][y]==1){
- return false; // if 1 means cell blocked
- }
- return true;
- }
- int shortestDistance(int sr, int sc, int dr, int dc){
- if(sr==dr && sc==dc){
- return 0;
- }
- map<pair<int,int> ,bool> visited;
- queue<pair<int,int>> Q;
- Q.push({sr,sc});
- visited[{sr,sc}]=true;
- int steps=0;
- while(!Q.empty()){
- steps++;
- int levelSize=Q.size();
- for(int i=0;i<levelSize;i++){
- int x=Q.front().first;
- int y=Q.front().second;
- vector<int> var={-1,1};
- for(int j=0;j<2;j++){ // left,right
- int newY=y+var[j];
- if(valid(x,newY)){
- if(x==dr && newY==dc){
- return steps; // if des is reached
- }
- if(visited[{x,newY}]!=true){
- Q.push({x,newY});
- visited[{x,newY}]=true;
- }
- }
- }
- for(int j=0;j<2;j++){ // up,down
- int newX=x+var[j];
- if(valid(newX,y)){
- if(newX==dr && y==dc){
- return steps; // if dest is reached
- }
- if(visited[{newX,y}]!=true){
- Q.push({newX,y});
- visited[{newX,y}]=true;
- }
- }
- }
- Q.pop(); // remove current element
- }
- }
- return -1; // no path
- }
- int main(){
- int t;
- cin>>t;
- while(t--){
- int r,c;
- cin>>r>>c;
- grid.resize(r);
- for(int i=0;i<r;i++){
- grid[i].resize(c);
- for(int j=0;j<c;j++){
- cin>>grid[i][j];
- }
- }
- int sr,sc,dr,dc;
- cin>>sr>>sc;
- cin>>dr>>dc;
- cout<<shortestDistance(sr,sc,dr,dc)<<endl;
- grid.resize(0); // reset grid
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment