腐烂的橘子

994. 腐烂的橘子

在给定的 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

相似题目

墙与门

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int orangesRotting(vector<vector<int>>& grid) { } };

rust 解法, 执行用时: 2 ms, 内存消耗: 2.1 MB, 提交时间: 2024-05-13 09:13:06

impl Solution {
    pub fn oranges_rotting(mut grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len();
        let n = grid[0].len();
        let mut fresh = 0;
        let mut q = vec![];
        for (i, row) in grid.iter().enumerate() {
            for (j, &x) in row.iter().enumerate() {
                if x == 1 {
                    fresh += 1;  // 统计新鲜橘子个数
                } else if x == 2 {
                    q.push((i, j));  // 一开始就腐烂的橘子
                }
            }
        }

        let mut ans = -1;
        while !q.is_empty() {
            ans += 1; // 经过一分钟
            let mut nxt = vec![];
            for (x, y) in q { // 已经腐烂的橘子
                for (i, j) in [(x.saturating_sub(1), y), (x + 1, y), (x, y.saturating_sub(1)), (x, y + 1)] { // 四方向
                    if i < m && j < n && grid[i][j] == 1 { // 新鲜橘子
                        fresh -= 1;
                        grid[i][j] = 2; // 变成腐烂橘子
                        nxt.push((i, j));
                    }
                }
            }
            q = nxt;
        }

        if fresh == 0 { ans.max(0) } else { -1 }
    }
}

javascript 解法, 执行用时: 68 ms, 内存消耗: 54.4 MB, 提交时间: 2024-05-13 09:12:53

/**
 * @param {number[][]} grid
 * @return {number}
 */
var orangesRotting = function(grid) {
    const m = grid.length;
    const n = grid[0].length;
    let fresh = 0;
    let q = [];
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (grid[i][j] === 1) {
                fresh++; // 统计新鲜橘子个数
            } else if (grid[i][j] === 2) {
                q.push([i, j]); // 一开始就腐烂的橘子
            }
        }
    }

    let ans = -1;
    while (q.length) {
        ans++; // 经过一分钟
        const tmp = q;
        q = [];
        for (const [x, y] of tmp) { // 已经腐烂的橘子
            for (const [i, j] of [[x - 1, y], [x + 1, y], [x, y - 1], [x, y + 1]]) { // 四方向
                if (0 <= i && i < m && 0 <= j && j < n && grid[i][j] === 1) { // 新鲜橘子
                    fresh--;
                    grid[i][j] = 2; // 变成腐烂橘子
                    q.push([i, j]);
                }
            }
        }
    }

    return fresh ? -1 : Math.max(ans, 0);
};

cpp 解法, 执行用时: 6 ms, 内存消耗: 15.5 MB, 提交时间: 2024-05-13 09:12:38

class Solution {
    int DIRECTIONS[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 四方向

public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int fresh = 0;
        vector<pair<int, int>> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    fresh++; // 统计新鲜橘子个数
                } else if (grid[i][j] == 2) {
                    q.emplace_back(i, j); // 一开始就腐烂的橘子
                }
            }
        }

        int ans = -1;
        while (!q.empty()) {
            ans++; // 经过一分钟
            vector<pair<int, int>> nxt;
            for (auto& [x, y] : q) { // 已经腐烂的橘子
                for (auto d : DIRECTIONS) { // 四方向
                    int i = x + d[0], j = y + d[1];
                    if (0 <= i && i < m && 0 <= j && j < n && grid[i][j] == 1) { // 新鲜橘子
                        fresh--;
                        grid[i][j] = 2; // 变成腐烂橘子
                        nxt.emplace_back(i, j);
                    }
                }
            }
            q = move(nxt);
        }

        return fresh ? -1 : max(ans, 0);
    }
};

java 解法, 执行用时: 1 ms, 内存消耗: 41.5 MB, 提交时间: 2024-05-13 09:12:17

class Solution {
    private static final int[][] DIRECTIONS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 四方向

    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int fresh = 0;
        List<int[]> q = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    fresh++; // 统计新鲜橘子个数
                } else if (grid[i][j] == 2) {
                    q.add(new int[]{i, j}); // 一开始就腐烂的橘子
                }
            }
        }

        int ans = -1;
        while (!q.isEmpty()) {
            ans++; // 经过一分钟
            List<int[]> tmp = q;
            q = new ArrayList<>();
            for (int[] pos : tmp) { // 已经腐烂的橘子
                for (int[] d : DIRECTIONS) { // 四方向
                    int i = pos[0] + d[0];
                    int j = pos[1] + d[1];
                    if (0 <= i && i < m && 0 <= j && j < n && grid[i][j] == 1) { // 新鲜橘子
                        fresh--;
                        grid[i][j] = 2; // 变成腐烂橘子
                        q.add(new int[]{i, j});
                    }
                }
            }
        }

        return fresh > 0 ? -1 : Math.max(ans, 0);
    }
}

python3 解法, 执行用时: 44 ms, 内存消耗: 16.4 MB, 提交时间: 2024-05-13 09:12:00

class Solution:
    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        fresh = 0
        q = []
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x == 1:
                    fresh += 1  # 统计新鲜橘子个数
                elif x == 2:
                    q.append((i, j))  # 一开始就腐烂的橘子

        ans = -1
        while q:
            ans += 1  # 经过一分钟
            tmp = q
            q = []
            for x, y in tmp:  # 已经腐烂的橘子
                for i, j in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1):  # 四方向
                    if 0 <= i < m and 0 <= j < n and grid[i][j] == 1:  # 新鲜橘子
                        fresh -= 1
                        grid[i][j] = 2  # 变成腐烂橘子
                        q.append((i, j))

        return -1 if fresh else max(ans, 0)

golang 解法, 执行用时: 4 ms, 内存消耗: 2.6 MB, 提交时间: 2021-07-20 10:32:25

// 994. 腐烂的橘子(扩散), 多源BFS
func orangesRotting(grid [][]int) int {
	if grid == nil || len(grid) == 0 {
		return 0
	}
	//按照上右下左方向进行扩展
	dx := []int{-1,0,1,0}
	dy := []int{0,1,0,-1}
	row, col := len(grid), len(grid[0])
	res := 0 //腐烂完成的时间
	queue := make([]int, 0)  // 腐烂的橘子

	for i := 0; i < row; i++ {
		for j := 0; j < col; j++ {
			if grid[i][j] == 2 {
				queue = append(queue, i*col+j) // 这种映射方式, 若j>=col, 会出错; 最好用 i * max(col, row) + j
			}
		}
	}
	// bfs搜索
	for len(queue) != 0 {
		res++ //每搜完一层，则时间加一分钟
		cursize := len(queue)//保存当前层的长度
		for i := 0; i < cursize; i++ {
			node := queue[0]
			queue = queue[1:]
			r, c := node/col, node%col
			for k := 0; k < 4; k++ {
				nr := r + dx[k]
				nc := c + dy[k]
				if nr >= 0 && nr < row && nc >= 0 && nc < col && grid[nr][nc] == 1 {
					grid[nr][nc] = 2  //将新鲜橘子腐烂
					queue = append(queue, nr*col+nc)//将腐烂橘子入队
				}
			}
		}
	}

	for i := 0; i < row; i++ {
		for j := 0; j < col; j++ {
			if grid[i][j] == 1 {
				return -1
			}
		}
	}

	if res == 0 {
		return res
	} 
	return res - 1
}

上一题

下一题

详情