Advertisement
Guest User

Untitled

a guest
Mar 25th, 2019
120
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.10 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement