snigdho386

Untitled

Sep 6th, 2025
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.17 KB | None | 0 0
  1. /*
  2. You have a maze represented as a 2D grid where:
  3.  
  4. 0 represents an empty space
  5. 1 represents a wall
  6. A ball is placed in this maze at a starting position. The ball follows these movement rules:
  7.  
  8. It can roll in four directions: up, down, left, or right
  9. Once the ball starts rolling in a direction, it keeps rolling until it hits a wall
  10. When the ball hits a wall, it stops and can then choose a new direction to roll
  11. Given:
  12.  
  13. A maze of size m x n
  14. A starting position start = [start_row, start_col]
  15. A destination position destination = [destination_row, destination_col]
  16. You need to determine if it's possible for the ball to stop at the destination position.
  17.  
  18. Important notes:
  19.  
  20. The ball must stop at the destination (not just pass through it)
  21. The borders of the maze are considered walls
  22. The ball can only stop when it hits a wall
  23. 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.
  24.  
  25. The function should return true if the ball can reach and stop at the destination, false otherwise.
  26.  
  27.  
  28. maze = [
  29.   [0, 0, 1, 0, 0],
  30.   [0, 0, 0, 0, 0],
  31.   [0, 0, 0, 1, 0],
  32.   [1, 1, 0, 1, 1],
  33.   [0, 0, 0, 0, 0]
  34. ]
  35. start = [0, 4]
  36. destination = [4, 4]
  37.  
  38.  
  39. Output: true
  40.  
  41. */
  42.  
  43.  
  44.  
  45. #include<bits/stdc++.h>
  46. using namespace std;
  47. #define int long long
  48.  
  49.  
  50. vector<vector<vector<int>>>vis;
  51. vector<vector<int>>a;
  52. int n,m;
  53. int sr,sc,dr,dc;
  54.  
  55.  
  56. // -2 for up
  57. // -1 for left
  58. //  1 for right
  59. //  2 for down
  60.  
  61.  
  62. bool dfs(int r,int c, int dir){
  63.    
  64.  
  65.     if(vis[r][c][dir]==1)
  66.         return false;    
  67.    
  68.     // Base case
  69.     if(r==dr && c==dc){
  70.        
  71.         cout<<" Hit ";
  72.         return true;
  73.     }
  74.  
  75.  
  76.     vis[r][c][dir] = 1;
  77.  
  78.     // Transitions
  79.  
  80.     // Any of the vertical
  81.     if(dir%2==0){
  82.  
  83.         if(dir==2){
  84.  
  85.             // Moving up
  86.             for(int k=r-1;k>=0;k--){
  87.                 if(a[k][c]==1 || k==0){
  88.                     return dfs(k,c,1)||dfs(k,c,3);
  89.                 }
  90.             }
  91.         }
  92.         else{
  93.  
  94.             // Moving down
  95.             for(int k=r+1;k<n;k++){
  96.                 if(a[k][c]==1 || k==n-1){
  97.                     return dfs(k,c,1)||dfs(k,c,3);
  98.                 }
  99.             }
  100.         }
  101.  
  102.     }else{
  103.  
  104.  
  105.         if(dir==1){
  106.  
  107.             // Moving left
  108.             for(int k=c-1;k>=0;k--){
  109.                 if(a[r][k]==1 || k==0){
  110.                     return dfs(r,k,2)||dfs(r,k,4);
  111.                 }
  112.             }
  113.  
  114.         }else{
  115.  
  116.             // Moving right
  117.             for(int k=c+1;k<m;k++){
  118.                 if(a[r][k]==1 || k==m-1){
  119.                     return dfs(r,k,2)||dfs(r,k,4);
  120.                    
  121.                 }
  122.             }
  123.  
  124.         }
  125.  
  126.     }
  127.    
  128.     return false;
  129.  
  130.  
  131.  
  132. }
  133.  
  134. signed main(){
  135.  
  136.     cin>>n>>m;
  137.  
  138.     a.resize(n,vector<int>(m));
  139.    
  140.     for(int i=0;i<n;i++){
  141.         for(int j=0;j<m;j++){
  142.            
  143.           cin>>a[i][j];
  144.         }
  145.     }
  146.  
  147.     cin>>sr>>sc;
  148.     cin>>dr>>dc;
  149.  
  150.  
  151.     vis.resize(n,vector<vector<int>>(m,vector<int>(5LL,0)));
  152.    
  153.  
  154.     cout<<(dfs(sr,sc,1)||dfs(sr,sc,2)||dfs(sr,sc,3)||dfs(sr,sc,4));
  155.  
  156. }
  157.  
  158.  
  159.  
Advertisement
Add Comment
Please, Sign In to add comment