Leetcode-1706. Where does the club fall

link

1706. Where the ball will go

subject

Use a size of m x n 2-D grid of grid It means a box . Do you have n Ball . The top and bottom of the box are open .

Each cell in the box has a diagonal baffle , Across the two corners of the cell , You can direct the ball to the left or right .

Guide the ball to the right baffle across the upper left and lower right , Use... In the grid 1 Express .
Guide the ball to the left baffle across the upper right and lower left , Use... In the grid -1 Express .
At the top of each box . Every ball can get stuck in the box or fall from the bottom . If the ball happens to be stuck between the two baffles "V" Shape patterns , Or guided by a block to either side of the box , It will get stuck .

Return a size of n Array of answer , among answer[i] On top of the ball is i The subscript of the column falling from the bottom after the column , If the ball gets stuck in the box , Then return to -1 .

Example

 

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]
explain ： The sample is shown in figure ：
b0 The ball starts to be in the second position 0 On the column , Finally from the bottom of the box 1 List out .
b1 The ball starts to be in the second position 1 On the column , It's going to get stuck in the second 2、3 Column and the first 1 Between lines "V" Xingli .
b2 The ball starts to be in the second position 2 On the column , It's going to get stuck in the second 2、3 Column and the first 0 Between lines "V" Xingli .
b3 The ball starts to be in the second position 3 On the column , It's going to get stuck in the second 2、3 Column and the first 0 Between lines "V" Xingli .
b4 The ball starts to be in the second position 4 On the column , It's going to get stuck in the second 2、3 Column and the first 1 Between lines "V" Xingli .

Example 2：
Input ：grid = [[-1]]
Output ：[-1]
explain ： The ball is stuck on the left side of the box .

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]
 

explain

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 100
• grid[i][j]  by  1  or  -1

Ideas （ simulation ）

According to the meaning , If the array element is 1, The baffle is inclined to the right , The ball will slide down and to the right , And the element value is -1 when , The baffle is inclined to the left , The ball will slide to the left . Then we can define a variable curcolumn Indicates which column the current ball is in , According to the current position, the baffle is 1 still -1, We can know which column the ball will move to next , that , Under what circumstances can the ball not reach the point ？ There are several situations ：

• 1. The ball moved to the left border , Stuck on the far left .（ You can imagine an extreme situation , The ball has been moving to the lower left from the beginning ）
• 2. Similar to the previous case , The ball moved to the boundary .
• 3. In another case, the ball is stuck between two baffles , To form the V type , And there are two cases , If the element of the current ball position is 1, That is, the baffle is inclined to the right , The ball is going to move to the lower right , Then if the element on the right of the current position is -1, That is, the baffle is inclined to the left , It forms a V, The ball cannot move . Another situation is , The element where the current ball position is located is -1, The baffle is inclined to the left , The ball is going to move to the lower left , Then you need to compare it with the baffle on the left , Judge whether it is V type , Only when these two baffle elements are consistent , That is to say, both are inclined to the left or to the right , It won't get stuck .

C++ Code

class Solution {
public:
    vector<int> findBall(vector<vector<int>>& grid) {
        int column=grid[0].size();// Total number of columns 
        vector<int> ans(column);// Store results 
        for(int i=0;i<column;i++)// Traverse each column 
        {
            int curcolumn= i; // Current number of columns 
            for(auto &row:grid) // Take out each line 
            {
                int move=row[curcolumn];
                curcolumn+=move;// Current column 
                if(curcolumn<0 || curcolumn>=column || move!=row[curcolumn]) // Beyond the border   perhaps   Formed an included angle V
                {
                    curcolumn=-1; break;
                }
            }
            ans[i] = curcolumn;
            
        }
        return ans;
    }
};