Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- You have a maze represented as a 2D grid where:
- 0 represents an empty space
- 1 represents a wall
- A ball is placed in this maze at a starting position. The ball follows these movement rules:
- It can roll in four directions: up, down, left, or right
- Once the ball starts rolling in a direction, it keeps rolling until it hits a wall
- When the ball hits a wall, it stops and can then choose a new direction to roll
- Given:
- A maze of size m x n
- A starting position start = [start_row, start_col]
- A destination position destination = [destination_row, destination_col]
- You need to determine if it's possible for the ball to stop at the destination position.
- Important notes:
- The ball must stop at the destination (not just pass through it)
- The borders of the maze are considered walls
- The ball can only stop when it hits a wall
- For example, if the ball is rolling right, it will continue moving right through all empty spaces (0) until it reaches a wall (1) or the maze boundary, at which point it stops and can choose a new direction.
- The function should return true if the ball can reach and stop at the destination, false otherwise.
- maze = [
- [0, 0, 1, 0, 0],
- [0, 0, 0, 0, 0],
- [0, 0, 0, 1, 0],
- [1, 1, 0, 1, 1],
- [0, 0, 0, 0, 0]
- ]
- start = [0, 4]
- destination = [4, 4]
- Output: true
- */
- #include<bits/stdc++.h>
- using namespace std;
- #define int long long
- vector<vector<vector<int>>>vis;
- vector<vector<int>>a;
- int n,m;
- int sr,sc,dr,dc;
- // -2 for up
- // -1 for left
- // 1 for right
- // 2 for down
- bool dfs(int r,int c, int dir){
- if(vis[r][c][dir]==1)
- return false;
- // Base case
- if(r==dr && c==dc){
- cout<<" Hit ";
- return true;
- }
- vis[r][c][dir] = 1;
- // Transitions
- // Any of the vertical
- if(dir%2==0){
- if(dir==2){
- // Moving up
- for(int k=r-1;k>=0;k--){
- if(a[k][c]==1 || k==0){
- return dfs(k,c,1)||dfs(k,c,3);
- }
- }
- }
- else{
- // Moving down
- for(int k=r+1;k<n;k++){
- if(a[k][c]==1 || k==n-1){
- return dfs(k,c,1)||dfs(k,c,3);
- }
- }
- }
- }else{
- if(dir==1){
- // Moving left
- for(int k=c-1;k>=0;k--){
- if(a[r][k]==1 || k==0){
- return dfs(r,k,2)||dfs(r,k,4);
- }
- }
- }else{
- // Moving right
- for(int k=c+1;k<m;k++){
- if(a[r][k]==1 || k==m-1){
- return dfs(r,k,2)||dfs(r,k,4);
- }
- }
- }
- }
- return false;
- }
- signed main(){
- cin>>n>>m;
- a.resize(n,vector<int>(m));
- for(int i=0;i<n;i++){
- for(int j=0;j<m;j++){
- cin>>a[i][j];
- }
- }
- cin>>sr>>sc;
- cin>>dr>>dc;
- vis.resize(n,vector<vector<int>>(m,vector<int>(5LL,0)));
- cout<<(dfs(sr,sc,1)||dfs(sr,sc,2)||dfs(sr,sc,3)||dfs(sr,sc,4));
- }
Advertisement
Add Comment
Please, Sign In to add comment