• API
• FAQ
• Tools
• Archive
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.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.

Top