算法---腐烂的橘子

本文主要是介绍算法---腐烂的橘子，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

示例 1：

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
示例 3：

输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] 仅为 0、1 或 2

解决方法

    fun orangesRotting(grid: Array<IntArray>): Int {//统计有几个没坏的var notBad = 0//把坏的坐标记录进队列val listBad = LinkedList<IntArray>()val bad = 2val good = 1grid.forEachIndexed { row, ints ->ints.forEachIndexed { col, i ->when (i) {good -> {notBad++}bad -> {listBad += intArrayOf(row, col)}else -> {}}}}var direction = arrayOf(intArrayOf(0, -1),intArrayOf(-1, 0),intArrayOf(0, 1),intArrayOf(1, 0),)//记录轮次var count = 0//不停的取出来while (listBad.isNotEmpty() && notBad != 0) {val size = listBad.sizefor (i in 1..size) {val first = listBad.pollFirst()for (array in direction) {if (first[0] + array[0] in grid.indices && first[1] + array[1] in grid[0].indices) {when (grid[first[0] + array[0]][first[1] + array[1]]) {good -> {listBad.addLast(intArrayOf(first[0] + array[0], first[1] + array[1]))grid[first[0] + array[0]][first[1] + array[1]] = 2notBad--}bad -> {//不是我传染的 我不应该管吧 不然死循环了}else -> {}}}}}count++}//判断没坏的是不是等于0 等于0 返回次数 否则返回-1return if (notBad == 0) count else -1}

总结

1.注意：当传播到最后一轮，只要没有了好橘子，那么就算队列里面不是空的，也没有必要继续传播了。

这么难得题，我竟然想法完全没错。我真猛啊

现在面试算法不成大问题了，但是感觉项目经历亮点不够，导致不太好找。
慢慢来吧，算法不能丢，项目慢慢做。

这篇关于算法---腐烂的橘子的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---