本文共 5436 字，大约阅读时间需要 18 分钟。

关注我，学习常用算法与数据结构，一题多解，降维打击。

题目描述

[1706]

• https://leetcode-cn.com/problems/where-will-the-ball-fall/

用一个大小为 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] 解释：球被卡在箱子左侧边上。

提示：

m == grid.length

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

题目剖析&信息挖掘

此题为图论题，考查对于图论模型建模的能力。

转化到图论模型后，可以用并查集解决。 也可以用DFS, 加上记忆化搜索，其实就是动态规划。

解题思路

此题的关键是如何将矩阵中的格子关系用图论的方法表示出来。

观察例子可以发现，一个小球只会停在格子的上半分部，一个球在一个格子里有2种状态。

要不挡板朝开口左，要不朝右。

设当前小球在row, col

当开口朝左时，我们要判断左边格子的开口朝向，如果相同则可以滚到row+1, col+1(与朝向相同，可以优化)说明（row, col） 和(row+1, col+1)是连通的。

当开口朝右也是同理。

如果开口不同向，就是卡住了。

有了以上基础就建立了图模型。

方法一 并查集

还不会，赶紧来学习吧

解析

由于题目说小球要滚出箱子才算出去，那我们先在箱子下面增加一行。

有了上面的力模型，我们的问题就变成第0排的格子与最后一排第n排中的某个格子相连通。

并查集是点与点的关系，要把每个格子看作一个点，对其进行编号像图一样（可以把二维的数组看成是一维的），其公式为row*m+col。

思路

/*并查集，判连通用*/type UnionFindSet struct {
   	father  []int // 存储结点的父亲	height  []int // 存储结点的父亲	nodeNum int   // 总结点个数}func (us *UnionFindSet) InitUnionSet(n int) {
   	}// 查询父结点func (us *UnionFindSet) Find(x int) int {
   	}//合并结点func (us *UnionFindSet) Union(x, y int) bool {
   	}//编号公式func getIndexByRowAndColumn(row, col, m int) int {
   	}func findBall(grid [][]int) []int {
   	n, m := len(grid), len(grid[0])	us := &UnionFindSet{
   }	us.InitUnionSet((n + 2) * m)	for i, row := range grid {
   		for j, v := range row {
         // 判断是否出界            // 判断是否有开口			us.Union(getIndexByRowAndColumn(i, j, m), getIndexByRowAndColumn(i+1, j+v, m))		}	}	ans := make([]int, m)  // 一重循环，对合并是有要求的。具体看代码	for i, _ := range ans {
   		buttomIndex := us.FindV2(getIndexByRowAndColumn(0, i, m))		if buttomIndex/m == n {
    // 如果是最后一行，就是有答案			ans[i]=buttomIndex%m		} else {
    // 没答案			ans[i]=-1		}	}	return ans}

注意

• 查看左右时，一定要先判断边界
• 合并时要把大的编号作为父亲结点，不用的话，最后一步要用2重循环，总体的复杂度还是m*n。影响是不大。

知识点

• 矩阵转数组
• 并查集
• 数组

复杂度

• 时间复杂度：O(n*m)
• 空间复杂度：O(n*m)

参考

代码实现

/*并查集，判连通用*/type UnionFindSet struct {
   	father  []int // 存储结点的父亲	nodeNum int   // 总结点个数}func (us *UnionFindSet) InitUnionSet(n int) {
   	us.nodeNum = n + 1 // 不加也可以，有人喜欢以0开头	us.father = make([]int, us.nodeNum)	for i, _ := range us.father {
   		us.father[i] = i	}}func (us *UnionFindSet) FindV2(x int) int {
   	root := x // 保存好路径上的头结点	for us.father[root] != root {
   		root = us.father[root]	}	/*		从头结点开始一直往根上遍历		把所有结点的father直接指向root。	*/	for us.father[x] != x {
   		// 一定要先保存好下一个结点，下一步是要对us.father[x]进行赋值		temp := us.father[x]		us.father[x] = root		x = temp	}	return root}//合并结点func (us *UnionFindSet) UnionV2(x, y int) bool {
   	x = us.FindV2(x)	y = us.FindV2(y)	if x == y {
   		return false	}	// 要保证根部是最底下的格子。	if x > y {
   		us.father[y] = x	} else {
   		us.father[x] = y	}	return true}func getIndexByRowAndColumn(row, col, m int) int {
   	return row*m + col}func findBall(grid [][]int) []int {
   	n, m := len(grid), len(grid[0])	us := &UnionFindSet{
   }	us.InitUnionSet((n + 2) * m)	for i, row := range grid {
   		for j, v := range row {
               //判断边界			if j+v < 0 || j+v >= m {
   				continue			}            // 判断是否 V型			if row[j+v] != v {
   				continue			}			us.UnionV2(getIndexByRowAndColumn(i, j, m), getIndexByRowAndColumn(i+1, j+v, m))		}	}	ans := make([]int, m)	for i, _ := range ans {
   		buttomIndex := us.FindV2(getIndexByRowAndColumn(0, i, m))		if buttomIndex/m == n {
    // 到达最后一行			ans[i]=buttomIndex%m		} else {
   			ans[i]=-1		}	}	return ans}

方法二 动态规划

可以学习一下

解析

还是要以一开始的图模型为基础。

设dp(i, j) 为i行j列的小球最终去哪里。 dp(n,j) = j (n是附加上的一行，已经在外面了，所以直接是答案) dp(i, j) 需要看所在格子的开口情况，看隔壁是否为V型，如果是答案是-1 否 dp(i, j) = dp(i+1, j+grip[i][j+grip[i][j]]) 转移。 注意要判断边界

思路

var vis [][]bool // 标记是否查询过var dpVal [][]int // 答案值func dp(row, col, n, m int, grid [][]int) int {
   	}func InitDp(n, m int) {
   }func findBall(grid [][]int) []int {
   	n, m := len(grid), len(grid[0])	InitDp(n, m)	ans := make([]int, m)	for i, _ := range ans {
   		ans[i] = dp(0, i, n, m, grid)	}	return ans}

注意

• 查看左右时，一定要先判断边界
• 当row=n时就是从底部落下了，所以当时col就是答案

知识点

• 矩阵转数组
• 动态规划
• 记忆化搜索

复杂度

• 时间复杂度：O(n*m)
• 空间复杂度：O(n*m)

参考

代码实现

var vis [][]bool // 标记是否查询过var dpVal [][]int // 答案值func dp(row, col, n, m int, grid [][]int) int {
   	if col < 0 || col >= m {
    // 出界了没有答案		return -1	}	if row == n {
    // 到底部了直接返答案		return col	} // 已经出界直接返回  	vis[row][col] = true	dpVal[row][col] = -1 // 默认无答案	// 判断边界，且2边是否形成V型	if col+grid[row][col] < 0 || col+grid[row][col] >= m || grid[row][col] != grid[row][col+grid[row][col]] {
    // 是V型直接返回		return dpVal[row][col]	}	dpVal[row][col] = dp(row+1, col+grid[row][col], n, m, grid) // 查看下一层	return dpVal[row][col]}func InitDp(n, m int) {
   	vis = make([][]bool, n+1)	dpVal = make([][]int, n+1)	for i := 0; i < n+1; i++ {
   		vis[i] = make([]bool, m)		dpVal[i] = make([]int, m)	}}func findBall(grid [][]int) []int {
   	n, m := len(grid), len(grid[0])	InitDp(n, m)	ans := make([]int, m)	for i, _ := range ans {
   		ans[i] = dp(0, i, n, m, grid)	}	return ans}

相关题目

这里整理了资料

动态规划相关题目

---

本人码农，希望通过自己的分享，让大家更容易学懂计算机知识。

转载地址：http://fowrz.baihongyu.com/