Well explained | Intuitive | C++ | DFS solution
Every cell of the grid is divided into top and bottom parts.  Algorithm can be devised by mere observation.\n1. If top =1 this means we are in the upper part of
Every cell of the grid is divided into top and bottom parts.  Algorithm can be devised by mere observation.\n1. If top =1 this means we are in the upper part of grid[i][j]. \n\t*  if grid[i][j]=1 \n\t\t*  We have to go to the bottom part of right cell. If that cell is out of bounds return -1.\n\t\t*  if grid[i][j+1] is not 1 then we cannot go further and are blocked. return -1\n\n\t*  if grid[i][j]=-1 \n\t\t*  We have to go to the bottom part of left cell. If that cell is out of bounds return -1.\n\t\t*  if grid[i][j-1] is not 1 then we cannot go further and are blocked. return -1\n\n2. If top =0 this means we are in the lower part of grid[i][j]. In such a case no matter the value of grid[i][j] we need to go down.\n\n3. If we reach bottom part of last row then return column number. \n\n4. !top means in next function call state will change from top to bottom and vice-versa. \n\n```\nclass Solution {\npublic:\n    int util(vector<vector<int>>&grid,bool top,int i,int j)\n    {   \n        if(top==0&&i==grid.size()-1)return j;\n        if(top==1)\n        {\n            if(grid[i][j]==1)\n            {   \n                if(j+1>=grid[0].size()||grid[i][j+1]==-1)return -1;\n                return util(grid,!top,i,j+1);\n            }\n            else\n            {\n                if(j-1<0||grid[i][j-1]==1)return -1;\n                return util(grid,!top,i,j-1);\n            }\n        }\n        else\n        {\n            return util(grid,!top,i+1,j);\n        }        \n    }\n    vector<int> findBall(vector<vector<int>>& grid) {\n        vector<int>ans(grid[0].size(),-1);\n        for(int i=0;i<grid[0].size();i++)\n        {\n            ans[i]=util(grid,true,0,i);\n        }\n        return ans;\n    }\n};\n```\n\nPlease upvote and share if you find the explanation useful.
['Depth-First Search', 'Recursion', 'C']