SHARE
TWEET

Untitled

a guest Mar 25th, 2019 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // DCG 23
  5.  
  6. // You are given an M by N matrix consisting of booleans that represents a board.
  7. // Each True boolean represents a wall. Each False boolean represents a tile you can walk on.
  8.  
  9. // Given this matrix, a start coordinate, and an end coordinate,
  10. // return the minimum number of steps required to reach the end coordinate from the start.
  11. // If there is no possible path, then return null. You can move up, left, down, and right.
  12. // You cannot move through walls. You cannot wrap around the edges of the board.
  13.  
  14. // For example, given the following board:
  15.  
  16. // [[f, f, f, f],
  17. // [t, t, f, t],
  18. // [f, f, f, f],
  19. // [f, f, f, f]]
  20. // and start = (3, 0) (bottom left) and end = (0, 0) (top left), the minimum number of steps
  21. // required to reach the end is 7, since we would need to go through (1, 2) because there is a
  22. // wall everywhere else on the second row.
  23.  
  24. // input:
  25. // 1
  26. // 4 4
  27. // 0 0 0 0
  28. // 1 1 0 1
  29. // 0 0 0 0
  30. // 0 0 0 0
  31. // 3 0
  32. // 0 0
  33.  
  34. // output:
  35. // 7
  36.  
  37. vector< vector<int> > mat; // global
  38.  
  39. bool valid(int x, int y){
  40.     if(x<0 || y<0 || x>=mat.size() || y>=mat[0].size() || mat[x][y] == 1){
  41.         return false;
  42.     }
  43.     return true;
  44. }
  45.  
  46. int minSteps(int sx,int sy, int dx, int dy){
  47.     if(sx == dx && sy == dy){
  48.         return 0; // base case
  49.     }
  50.     queue< pair<int,int> > Q;
  51.     map< pair<int,int>, bool > visited;
  52.     Q.push({sx,sy});
  53.     visited[{sx,sy}]=true;
  54.     int steps = 0;
  55.     while( !Q.empty() ){
  56.         int levelSize = Q.size();
  57.         steps++;
  58.         while(levelSize--){
  59.             int currx = Q.front().first;
  60.             int curry = Q.front().second;
  61.             Q.pop();
  62.             vector<int> comb = {-1,1};
  63.             for(int i=0;i<2;i++){ // top, down
  64.                     int newx=currx+comb[i];
  65.                     if( valid(newx,curry) ){
  66.                         if(newx == dx && curry == dy){
  67.                             return steps;
  68.                         }
  69.                         if( !visited[{newx,curry}]){
  70.                             Q.push({newx,curry});
  71.                             visited[{newx,curry}]=true;
  72.                         }
  73.                     }
  74.             }
  75.             for(int i=0;i<2;i++){ // left, right
  76.                     int newy=curry+comb[i];
  77.                     if( valid(currx,newy) ){
  78.                         if(currx == dx && newy == dy){
  79.                             return steps;
  80.                         }
  81.                         if( !visited[{currx,newy}]){
  82.                             Q.push({currx,newy});
  83.                             visited[{currx,newy}]=true;
  84.                         }
  85.                     }
  86.             }
  87.         }
  88.     }
  89.     return -1;
  90. }
  91.  
  92. int main(){
  93.     freopen("ip.txt","r",stdin);
  94.     int t;
  95.     cin>>t;
  96.     while(t--){
  97.         int r,c;
  98.         cin>>r>>c;
  99.         mat.resize(r);
  100.         for(int i=0;i<r;i++){
  101.             mat[i].resize(c);
  102.             for(int j=0;j<c;j++){
  103.                 // 1-block, 0-path
  104.                 cin>>mat[i][j];
  105.             }
  106.         }
  107.         int sx,sy,dx,dy;
  108.         cin>>sx>>sy;
  109.         cin>>dx>>dy;
  110.         cout<<minSteps(sx,sy,dx,dy)<<endl;;
  111.         mat.resize(0);
  112.     }
  113.     return 0;
  114. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top