题目
题目链接:
https://www.nowcoder.com/practice/54ab9865ce7a45968b126d6968a77f34
思路
广度优先搜索。首先找到2坐标集合,然后每次往四周为1的坐标扩展
参考答案Java
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param grid int整型ArrayList<ArrayList<>>
* @return int整型
*/
public int rotApple (ArrayList<ArrayList<Integer>> grid) {
//BFS
int n = grid.size();
int m = grid.get(0).size();
Queue<Integer> q2 = new LinkedList<>();
int total1 = 0; //正常的苹果个数
for (int i = 0; i < n ; i++) {
for (int j = 0; j < m ; j++) {
if (grid.get(i).get(j) == 2) {
q2.add(i * m + j);
}
if (grid.get(i).get(j) == 1) {
total1++;
}
}
}
int[] dirx = {-1, 1, 0, 0};
int[] diry = {0, 0, -1, 1};
int deep = 0;
int change2 = 0; //变为腐烂的苹果的个数
while (!q2.isEmpty()) {
int size = q2.size();
for (int i = 0; i < size ; i++) {
int xy = q2.poll();
int x1 = xy / m; //横坐标
int y1 = xy % m; //纵坐标
for (int j = 0; j < 4 ; j++) {
int x2 = x1 + dirx[j];
int y2 = y1 + diry[j];
if (x2 >= 0 && x2 < n && y2 >= 0 && y2 < m && grid.get(x2).get(y2) == 1) {
q2.add(x2 * m + y2);
change2++;
grid.get(x2).set(y2, 2);
}
}
}
deep++;
}
if (change2 != total1) return -1; //正常的苹果没有全部腐烂,返回-1
return deep - 1;
}
}
参考答案Go
package main
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param grid int整型二维数组
* @return int整型
*/
func rotApple(grid [][]int) int {
// BFS
n := len(grid)
m := len(grid[0])
total1 := 0 //正常的苹果个数
q2 := []int{} //切片模拟队列
for i := 0; i < n; i++ {
for j := 0; j < m; j++ {
if grid[i][j] == 2 {
q2 = append(q2, i*m+j)
}
if grid[i][j] == 1 {
total1++
}
}
}
change2 := 0 //正常苹果变为腐烂苹果的个数
deep := 0
dirx := []int{-1, 1, 0, 0}
diry := []int{0, 0, -1, 1}
for len(q2) > 0 {
size := len(q2)
q2new := []int{}
for i := 0; i < size; i++ {
xy := q2[i]
x1 := xy / m //xy对应的 横坐标
y1 := xy % m //xy对应的纵坐标
for j := 0; j < 4; j++ {
x2 := x1 + dirx[j]
y2 := y1 + diry[j]
if x2 >= 0 && x2 < n && y2 >= 0 && y2 < m && grid[x2][y2] == 1 {
grid[x2][y2] = 2
change2++
q2new = append(q2new, x2*m+y2)
}
}
}
q2 = q2new
deep++
}
if change2 != total1 {
return -1
}
return deep - 1
}