牛客 2024春招冲刺题单 ONT82 腐烂的苹果【中等 BFS Java,Go】

题目

题目链接：
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
}

原文地址：https://blog.csdn.net/weixin_37991016/article/details/137523956

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！