C++ solution || recursive || Explained
Intuition\n Describe your first thoughts on how to solve this problem. \nThis is a simulation problem, something like the path finding problem. This will help y
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis is a simulation problem, something like the path finding problem. This will help you to think of a recursive solution considering all possible paths.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nTake a variable that helps you to keep track of the ball number(which column the ball is entering). Iterate for all the balls.\n\nNow, for each ball we need to find an exit point or trap point. So as we move into the recursive function, if our current cell has a 1, it means \'\\\' and a -1 means \'/\'. So, getting a 1 would lead us to the (i+1,j+1) cell while the -1 would lead us to (i+1,j-1). So, accordingly we use the recursive calls.\n\nBASE CASES/EDGE CASES:\nthe ball falls out(i >= m>) -> return the column number.\n\nelse for all other cases -> return -1.\nThese cases include:\n1) V formation -> grid[i][j] == 1 && grid[i][j+1] == -1 and Vice-Versa.\n2) Edge blocks -> grid[i][j] == 1 and j+1 >= n and Vice-Versa.\n\nStore the answers in a vector and return the vector as solution.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(M*N)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nIf a recursive soln is considered, the auxiliary stack space would be O(M). Memoization takes O(M*N).\n\n# Code\n```\nclass Solution {\npublic:\n    int solve(int i,int j,vector<vector<int>>& grid,int m,int n,vector<vector<int>> &dp)\n    {\n        if(i >= m) return j;\n\n        if(dp[i][j] != -1) return dp[i][j]; \n\n        if(grid[i][j] == 1 && j+1 < n && grid[i][j+1] == 1)\n        return dp[i][j] = solve(i+1,j+1,grid,m,n,dp);\n\n        if(grid[i][j] == -1 && j-1 >= 0 && grid[i][j-1] == -1)\n        return dp[i] [j] = solve(i+1,j-1,grid,m,n,dp);  \n\n        return dp[i][j] = -1;\n    }\n     \n    vector<int> findBall(vector<vector<int>>& grid) {\n        int ball_no;\n        int rows = grid.size();\n        int cols = grid[0].size();\n\n        vector<vector<int>> dp(rows,vector<int>(cols,-1));\n\n        vector<int> ans(cols);\n        for(ball_no = 0; ball_no < cols ; ball_no++)\n        {\n            ans[ball_no] = solve(0,ball_no,grid,rows,cols,dp);\n        }\n        return ans;\n    }\n};\n```
['C++']