题目
在给定的 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.注意:当传播到最后一轮,只要没有了好橘子,那么就算队列里面不是空的,也没有必要继续传播了。
这么难得题,我竟然想法完全没错。我真猛啊
现在面试算法不成大问题了,但是感觉项目经历亮点不够,导致不太好找。
慢慢来吧,算法不能丢,项目慢慢做。