Guest User

Untitled

a guest
Nov 15th, 2018
90
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.17 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // #Graph #BFS
  5. // given a maze and source and destination return min steps reqd
  6.  
  7. vector<vector<int> > grid; // global
  8.  
  9.  
  10. bool valid(int x,int y){
  11. // [0,n-1] for 0 indexed
  12. if(x<0 || y<0 || x>=grid.size() || y>=grid[0].size() || grid[x][y]==1){
  13. return false; // if 1 means cell blocked
  14. }
  15. return true;
  16. }
  17. int shortestDistance(int sr, int sc, int dr, int dc){
  18. if(sr==dr && sc==dc){
  19. return 0;
  20. }
  21. map<pair<int,int> ,bool> visited;
  22. queue<pair<int,int>> Q;
  23. Q.push({sr,sc});
  24. visited[{sr,sc}]=true;
  25. int steps=0;
  26. while(!Q.empty()){
  27. steps++;
  28. int levelSize=Q.size();
  29. for(int i=0;i<levelSize;i++){
  30. int x=Q.front().first;
  31. int y=Q.front().second;
  32. vector<int> var={-1,1};
  33. for(int j=0;j<2;j++){ // left,right
  34. int newY=y+var[j];
  35. if(valid(x,newY)){
  36. if(x==dr && newY==dc){
  37. return steps; // if des is reached
  38. }
  39. if(visited[{x,newY}]!=true){
  40. Q.push({x,newY});
  41. visited[{x,newY}]=true;
  42. }
  43. }
  44. }
  45. for(int j=0;j<2;j++){ // up,down
  46. int newX=x+var[j];
  47. if(valid(newX,y)){
  48. if(newX==dr && y==dc){
  49. return steps; // if dest is reached
  50. }
  51. if(visited[{newX,y}]!=true){
  52. Q.push({newX,y});
  53. visited[{newX,y}]=true;
  54. }
  55. }
  56. }
  57. Q.pop(); // remove current element
  58. }
  59. }
  60. return -1; // no path
  61. }
  62.  
  63. int main(){
  64. int t;
  65. cin>>t;
  66. while(t--){
  67. int r,c;
  68. cin>>r>>c;
  69. grid.resize(r);
  70. for(int i=0;i<r;i++){
  71. grid[i].resize(c);
  72. for(int j=0;j<c;j++){
  73. cin>>grid[i][j];
  74. }
  75. }
  76. int sr,sc,dr,dc;
  77. cin>>sr>>sc;
  78. cin>>dr>>dc;
  79. cout<<shortestDistance(sr,sc,dr,dc)<<endl;
  80. grid.resize(0); // reset grid
  81. }
  82. return 0;
  83. }
Add Comment
Please, Sign In to add comment