You have a 2-D grid of size m x n representing a box, and you have n balls. The box is open on the top and bottom sides.

Each cell in the box has a diagonal board spanning two corners of the cell that can redirect a ball to the right or to the left.


	A board that redirects the ball to the right spans the top-left corner to the bottom-right corner and is represented in the grid as 1.
	A board that redirects the ball to the left spans the top-right corner to the bottom-left corner and is represented in the grid as -1.


We drop one ball at the top of each column of the box. Each ball can get stuck in the box or fall out of the bottom. A ball gets stuck if it hits a "V" shaped pattern between two boards or if a board redirects the ball into either wall of the box.

Return an array answer of size n where answer[i] is the column that the ball falls out of at the bottom after dropping the ball from the ith column at the top, or -1 if the ball gets stuck in the box.

&nbsp;
Example 1:



Input: grid = [[1,1,1,-1,-1],[1,1,1,-1,-1],[-1,-1,-1,1,1],[1,1,1,1,-1],[-1,-1,-1,-1,-1]]
Output: [1,-1,-1,-1,-1]
Explanation: This example is shown in the photo.
Ball b0 is dropped at column 0 and falls out of the box at column 1.
Ball b1 is dropped at column 1 and will get stuck in the box between column 2 and 3 and row 1.
Ball b2 is dropped at column 2 and will get stuck on the box between column 2 and 3 and row 0.
Ball b3 is dropped at column 3 and will get stuck on the box between column 2 and 3 and row 0.
Ball b4 is dropped at column 4 and will get stuck on the box between column 2 and 3 and row 1.


Example 2:

Input: grid = [[-1]]
Output: [-1]
Explanation: The ball gets stuck against the left wall.


Example 3:

Input: grid = [[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1],[1,1,1,1,1,1],[-1,-1,-1,-1,-1,-1]]
Output: [0,1,2,3,4,-1]


&nbsp;
Constraints:


	m == grid.length
	n == grid[i].length
	1 &lt;= m, n &lt;= 100
	grid[i][j] is 1 or -1.


class Solution:
    def findBall(self, grid: List[List[int]]) -> List[int]:

        m,n=len(grid),len(grid[0])
        for i in range(m):
            grid[i].insert(0,1)
            grid[i].append(-1)
        res=[]

        for k in range(1,n+1):
            i , j = 0 , k
            struck = False
            while i<m:
                if grid[i][j]==1:
                    if grid[i][j+1]==1:
                        j+=1
                    else:
                        struck=True
                        break
                else:
                    if grid[i][j-1]==-1:
                        j-=1
                    else:
                        struck=True
                        break
                i+=1
            if struck:
                res.append(-1)
            else:
                res.append(j-1)

        return res
class Solution {
    public int dfs(int[][] grid, int i, int j){
        if(i==grid.length)
            return j;

        if(j<0 || j>=grid[0].length)
            return -1;

        if(grid[i][j]==1 && j+1<grid[0].length && grid[i][j+1]==1)
            return dfs(grid,i+1,j+1);

        else if(grid[i][j]==-1 && j-1>=0 && grid[i][j-1]==-1)
            return dfs(grid,i+1,j-1);

        return -1;
    }
    public int[] findBall(int[][] grid) {
        int m = grid[0].length;
        int[] ar = new int[m];

        for(int j=0;j<m;j++)
            ar[j]=dfs(grid,0,j);

        return ar;
    }
}
class Solution {
public:
    int util(vector<vector<int>>&grid,bool top,int i,int j)
    {
        if(top==0&&i==grid.size()-1)return j;
        if(top==1)
        {
            if(grid[i][j]==1)
            {
                if(j+1>=grid[0].size()||grid[i][j+1]==-1)return -1;
                return util(grid,!top,i,j+1);
            }
            else
            {
                if(j-1<0||grid[i][j-1]==1)return -1;
                return util(grid,!top,i,j-1);
            }
        }
        else
        {
            return util(grid,!top,i+1,j);
        }
    }
    vector<int> findBall(vector<vector<int>>& grid) {
        vector<int>ans(grid[0].size(),-1);
        for(int i=0;i<grid[0].size();i++)
        {
            ans[i]=util(grid,true,0,i);
        }
        return ans;
    }
};
var findBall = function(grid) {
    let m = grid.length,
        n = grid[0].length,
        ans = []
    for (let start = 0; start < n; start++) {     // Iterate through the different starting conditions
        let j = start
        for (let i = 0; i < m; i++) {             // Then iterate downward from grid[i][j]
            let dir = grid[i][j]                  // Compare the direction of the current cell to the direction
            if (dir === grid[i][j+dir]) j += dir  //   of the cell on the slant side and move that way if matched
            else i = m, j = -1                    // Otherwise jump to the loop's end and set j to the fail value
        }
        ans[start] = j                            // Update the answer
    }
    return ans                                    // Return the completed answer
};
Where Will the Ball Fall