Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- // DCG 23
- // You are given an M by N matrix consisting of booleans that represents a board.
- // Each True boolean represents a wall. Each False boolean represents a tile you can walk on.
- // Given this matrix, a start coordinate, and an end coordinate,
- // return the minimum number of steps required to reach the end coordinate from the start.
- // If there is no possible path, then return null. You can move up, left, down, and right.
- // You cannot move through walls. You cannot wrap around the edges of the board.
- // For example, given the following board:
- // [[f, f, f, f],
- // [t, t, f, t],
- // [f, f, f, f],
- // [f, f, f, f]]
- // and start = (3, 0) (bottom left) and end = (0, 0) (top left), the minimum number of steps
- // required to reach the end is 7, since we would need to go through (1, 2) because there is a
- // wall everywhere else on the second row.
- // input:
- // 1
- // 4 4
- // 0 0 0 0
- // 1 1 0 1
- // 0 0 0 0
- // 0 0 0 0
- // 3 0
- // 0 0
- // output:
- // 7
- vector< vector<int> > mat; // global
- bool valid(int x, int y){
- if(x<0 || y<0 || x>=mat.size() || y>=mat[0].size() || mat[x][y] == 1){
- return false;
- }
- return true;
- }
- int minSteps(int sx,int sy, int dx, int dy){
- if(sx == dx && sy == dy){
- return 0; // base case
- }
- queue< pair<int,int> > Q;
- map< pair<int,int>, bool > visited;
- Q.push({sx,sy});
- visited[{sx,sy}]=true;
- int steps = 0;
- while( !Q.empty() ){
- int levelSize = Q.size();
- steps++;
- while(levelSize--){
- int currx = Q.front().first;
- int curry = Q.front().second;
- Q.pop();
- vector<int> comb = {-1,1};
- for(int i=0;i<2;i++){ // top, down
- int newx=currx+comb[i];
- if( valid(newx,curry) ){
- if(newx == dx && curry == dy){
- return steps;
- }
- if( !visited[{newx,curry}]){
- Q.push({newx,curry});
- visited[{newx,curry}]=true;
- }
- }
- }
- for(int i=0;i<2;i++){ // left, right
- int newy=curry+comb[i];
- if( valid(currx,newy) ){
- if(currx == dx && newy == dy){
- return steps;
- }
- if( !visited[{currx,newy}]){
- Q.push({currx,newy});
- visited[{currx,newy}]=true;
- }
- }
- }
- }
- }
- return -1;
- }
- int main(){
- freopen("ip.txt","r",stdin);
- int t;
- cin>>t;
- while(t--){
- int r,c;
- cin>>r>>c;
- mat.resize(r);
- for(int i=0;i<r;i++){
- mat[i].resize(c);
- for(int j=0;j<c;j++){
- // 1-block, 0-path
- cin>>mat[i][j];
- }
- }
- int sx,sy,dx,dy;
- cin>>sx>>sy;
- cin>>dx>>dy;
- cout<<minSteps(sx,sy,dx,dy)<<endl;;
- mat.resize(0);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement