球会落何处

难度: Medium

用一个大小为 m x n 的二维网格 grid 表示一个箱子。你有 n 颗球。箱子的顶部和底部都是开着的。

箱子中的每个单元格都有一个对角线挡板，跨过单元格的两个角，可以将球导向左侧或者右侧。

将球导向右侧的挡板跨过左上角和右下角，在网格中用 1 表示。
将球导向左侧的挡板跨过右上角和左下角，在网格中用 -1 表示。

在箱子每一列的顶端各放一颗球。每颗球都可能卡在箱子里或从底部掉出来。如果球恰好卡在两块挡板之间的 "V" 形图案，或者被一块挡导向到箱子的任意一侧边上，就会卡住。

返回一个大小为 n 的数组 answer ，其中 answer[i] 是球放在顶部的第 i 列后从底部掉出来的那一列对应的下标，如果球卡在盒子里，则返回 -1 。

示例 1：

输入：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]]
输出：[1,-1,-1,-1,-1]
解释：示例如图：
b0 球开始放在第 0 列上，最终从箱子底部第 1 列掉出。
b1 球开始放在第 1 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。
b2 球开始放在第 2 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b3 球开始放在第 3 列上，会卡在第 2、3 列和第 0 行之间的 "V" 形里。
b4 球开始放在第 4 列上，会卡在第 2、3 列和第 1 行之间的 "V" 形里。

示例 2：

输入：grid = [[-1]]
输出：[-1]
解释：球被卡在箱子左侧边上。

示例 3：

输入：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]]
输出：[0,1,2,3,4,-1]

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 100
grid[i][j] 为 1 或 -1

Submission

运行时间: 38 ms

内存: 16.5 MB

class Solution:
    def findBall(self, grid: List[List[int]]) -> List[int]:
        
        m, n = len(grid), len(grid[0])
        answer = [-1] * n

        for col in range(n):
            curr_col = col
            for row in range(m):
                dir = grid[row][curr_col]
                next_col = curr_col + dir
                # Check if the ball is out of bounds or hits a 'V' shaped pattern
                if next_col < 0 or next_col >= n or grid[row][next_col] != dir:
                    curr_col = -1
                    break
                curr_col = next_col
            if curr_col != -1:
                answer[col] = curr_col

        return answer

Explain

The solution simulates the path of each ball from the top of the grid to the bottom or until it gets stuck. For each ball, it starts at the top of a column and moves downwards. At each step, based on the direction of the current grid cell (either 1 for right or -1 for left), it tries to move to the adjacent column in that direction. If the ball attempts to move outside the grid bounds or into a cell whose direction forms a 'V' shape with the current cell's direction (i.e., the directions are opposite), the ball gets stuck, and the loop for that ball breaks. If a ball reaches the bottom without getting stuck, its final column position is recorded in the answer array. Otherwise, the position remains -1 indicating the ball got stuck.

时间复杂度: O(m * n)

空间复杂度: O(n)

class Solution:
    def findBall(self, grid: List[List[int]]) -> List[int]:
        m, n = len(grid), len(grid[0])  # Get the dimensions of the grid
        answer = [-1] * n  # Initialize the answer array with -1

        for col in range(n):  # Iterate over each ball
            curr_col = col  # Start position for the current ball
            for row in range(m):  # Simulate the ball movement row by row
                dir = grid[row][curr_col]  # Direction of the current cell
                next_col = curr_col + dir  # Calculate the next column based on direction
                # Check if the ball is out of bounds or hits a 'V' shaped pattern
                if next_col < 0 or next_col >= n or grid[row][next_col] != dir:
                    curr_col = -1  # Mark the ball as stuck
                    break  # Exit the loop as the ball is stuck
                curr_col = next_col  # Move the ball to the next column
            if curr_col != -1:
                answer[col] = curr_col  # Record the exit column if the ball is not stuck

        return answer  # Return the final results

Explore

在模拟球的路径时，如果球位于最左列或最右列，我们必须特别小心，因为球可能会试图移动到网格外。例如，如果球在最左列并且当前格的方向为-1（向左），或者球在最右列并且当前格的方向为1（向右），那么球将尝试移动到网格外，这是不允许的。在代码中，通过检查`next_col < 0 or next_col >= n`来处理这种边界情况，如果`next_col`的计算结果超出这个范围，就意味着球尝试移动到网格外，从而球会被设为卡住状态。

在代码中，确保行的遍历和对下一列的判断准确无误是通过仔细的条件检查实现的。每次球尝试移动到下一列时，首先检查这一移动是否会导致球移到网格外（`next_col < 0 or next_col >= n`）。此外，还需要检查球是否会进入一个与当前格方向相反的格子（形成'V'型）。这是通过`grid[row][next_col] != dir`来检查的。由于行的遍历是从0到m-1，且每次循环仅对当前行进行操作，因此不存在行索引错误或越界的问题。

在题解中，判断两个挡板方向相反的逻辑体现在检查条件`grid[row][next_col] != dir`中。这里的`dir`是当前格的方向，而`grid[row][next_col]`是球尝试移动到的下一个格子的方向。如果这两个值不相等，说明方向相反（一个为1，另一个为-1），形成'V'型。因此，这种情况下，球会卡住，循环将中断并且球的位置设置为-1。

数组`answer`中的初始化为`-1`主要是为了表示球被卡住的情况。在模拟开始之前，不清楚哪些球能够成功到达底部。因此，初始设定每个球的位置为-1，这样如果球在模拟过程中卡住，其位置就保持为-1。如果有球成功到达底部，其对应的位置会被更新为正确的列索引。这种初始化方法简单明了，直接反映球是否被卡住。尽管也可以用其他数值或标记初始化，但使用-1是因为它在逻辑上直接表明了“未成功到达”这一状态，且易于理解和实现。