大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

在一个箱子里面，每个格子都有一个沿着对角线的挡板（朝左或者朝右），如果两个挡板形成了 V 型，那么球就会卡住无法下落。

起始时，在箱子的最上面（第 $0$ 行）的每个格子里面都有一个小球，判断小球落到最下面时属于哪一列。如果小球无法到达最下面，那么对应值是 -1。

解题方法

DFS

看了眼题解区，都在用模拟法，类似于动态规划的思路。我这里提供一版容易理解的 DFS 思路。

小球在下落过程中的思路是什么呢？有哪几种可能呢？

  1. 如果当前的挡板是朝左的，并且小球位于最左列，这时会被箱子最左边的挡板挡住，那么小球不能继续下落。

image.png

  1. 如果当前的挡板是朝右的，并且小球位于最右列，这时会被箱子最右边的挡板挡住，那么小球不能继续下落。

image.png

  1. 如果小球当前的格子朝右的，但是同一行右边的格子朝左的，那么形成了 V型，小球无法下落；

image.png

  1. 如果小球当前的格子朝左的，但是同一行左边的格子朝右的，那么形成了 V型，小球无法下落；

image.png

  1. 在排除上面的情况后，小球可以下落到下一行：
    1. 如果当前格子朝右，小球会下落到下一行的右边一列；
    2. 如果当前格子朝左，小球会下落到下一行的左边一列；

image.png

  1. 如果小球到达最后一行，需要继续下落，确定掉出来的位置。思路与上一种情况相同。

image.png
上面就是所有的可能。

对于第 3 种、第 4 种可能性，即形成 V 型，可以统一表示为grid[i][j] != grid[i][j + grid[i][j]]。留给读者自己思考。

代码

定义函数 DFS(grid, i, j)，含义是判断处于 grid[i][j]位置的小球下一步会落到哪里（此时的 $i, j$ 是合法的）。

在DFS中，需要考虑上面各种情况，在小球仍能移动时，持续移动，直到小球不可移动（返回 $-1$）或者小球掉落出来（返回掉落的位置）。

三种语言的代码如下：

  1. class Solution {
  2.     int M, N;
  3.     public int[] findBall(int[][] grid) {
  4.         M = grid.length;
  5.         N = grid[0].length;
  6.         int[] res = new int[N];
  7.         for (int col = 0; col < N; ++col) {
  8.             res[col] = dfs(grid, 0, col);
  9.         }
  10.         return res;
  11.     }
  13.     public int dfs(int[][] grid, int i, int j) {
  14.         // 第 1 种情况：到达最右端，卡住
  15.         if (j == N - 1 && grid[i][j] == 1) 
  16.             return -1;
  17.         // 第 2 种情况：到达最左端，卡住
  18.         if (j == 0 && grid[i][j] == -1)
  19.             return -1;
  20.         // 第 3、4 种情况：形成 V 型，无法下落
  21.         if (grid[i][j] != grid[i][j + grid[i][j]])
  22.             return -1;
  23.         // 第 6 种情况：到达最后一行，需要继续下落
  24.         if (i == M - 1)
  25.             return j + grid[i][j];
  26.         // 第 5 种情况：未到达最后一行，继续下落
  27.         return dfs(grid, i + 1, j + grid[i][j]);
  28.     }
  29. }
  1. class Solution {
  2. private:
  3.     int M, N;
  4. public:
  5.     vector<int> findBall(vector<vector<int>>& grid) {
  6.         M = grid.size();
  7.         N = grid[0].size();
  8.         vector<int> res;
  9.         for (int col = 0; col < N; ++col) {
  10.             res.push_back(dfs(grid, 0, col));
  11.         }
  12.         return res;
  13.     }
  15.     int dfs(vector<vector<int>>& grid, int i, int j) {
  16.         // 第 1 种情况：到达最右端，卡住
  17.         if (j == N - 1 && grid[i][j] == 1) 
  18.             return -1;
  19.         // 第 2 种情况：到达最左端，卡住
  20.         if (j == 0 && grid[i][j] == -1)
  21.             return -1;
  22.         // 第 3、4 种情况：形成 V 型，无法下落
  23.         if (grid[i][j] != grid[i][j + grid[i][j]])
  24.             return -1;
  25.         // 第 6 种情况：到达最后一行，需要继续下落
  26.         if (i == M - 1)
  27.             return j + grid[i][j];
  28.         // 第 5 种情况：未到达最后一行，继续下落
  29.         return dfs(grid, i + 1, j + grid[i][j]);
  30.     }
  31. };
  1. class Solution(object):
  2.     def findBall(self, grid):
  3.         """
  4.         :type grid: List[List[int]]
  5.         :rtype: List[int]
  6.         """
  7.         M, N = len(grid), len(grid[0])
  8.         res = []
  9.         for col in range(N):
  10.             res.append(self.dfs(grid, 0, col))
  11.         return res
  13.     def dfs(self, grid, i, j):
  14.         M, N = len(grid), len(grid[0])
  15.         # 第 1 种情况：到达最右端，卡住
  16.         if grid[i][j] == 1 and j == N - 1:
  17.             return -1
  18.         # 第 2 种情况：到达最左端，卡住
  19.         if grid[i][j] == -1 and j == 0:
  20.             return -1
  21.         # 第 3、4 种情况：形成 V 型，无法下落
  22.         if grid[i][j] != grid[i][j + grid[i][j]]:
  23.             return -1
  24.         # 第 6 种情况：到达最后一行，需要继续下落
  25.         if i == M - 1:
  26.             return j + grid[i][j]
  27.         # 第 5 种情况：未到达最后一行，继续下落
  28.         return self.dfs(grid, i + 1, j + grid[i][j])

复杂度

  • 时间复杂度：1706. 球会落何处 - 图7，其中 1706. 球会落何处 - 图8 分别是数组的行、列数；
  • 空间复杂度： 1706. 球会落何处 - 图9#card=math&code=O%281%29&id=Pz3XE)

总结

  1. 这个题不难，但是需要考虑的情况略多。
  2. 这里的 DFS 就是一个递归，不断的求小球落到下一行的位置。

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。