leetcode994：腐烂的橘子

题目链接

leetcode

题目描述

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

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

C++ 代码

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (const vector<int>& num : nums) {
        cout << "[";
        for (const int& num2 : num) {
            cout << num2 << ",";
        }
        cout << "], ";
    }
    cout << "]" <<endl;
}

/*
   由题目可知，每分钟每个腐烂的橘子都会使上下左右相邻的新鲜橘子腐烂，
   这其实是一个模拟广度优先搜索的过程。

   广度优先搜索，就是从起点出发，每次都尝试访问同一层的节点。
   如果同一层都访问完了，再访问下一层，
   最后找到的路径就是从起点开始的最短合法路径。

    时间复杂度：O(mn)
        其中 m, n 分别为 grid 的行数与列数。
    空间复杂度：O(mn)
        数组记录每个新鲜橘子被腐烂的最短时间，需要 O(nm) 的空间。
        队列中存放的状态最多不会超过 mn 个，最多需要 O(nm) 的空间。
*/
class Solution {
public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        memset(badTime, -1, sizeof(badTime));
        queue<pair<int, int>> badOranges;
        
        // 遍历二维数组：腐烂的橘子存入队列，设置腐烂的时间，统计新鲜橘子的数量
        for (int i = 0; i < m; i ++) {
            for (int j = 0; j < n; j ++) {
                if (grid[i][j] == 2) {
                    badOranges.emplace(i, j);
                    badTime[i][j] = 0;
                } else if (grid[i][j] == 1) {
                    count ++;
                }
            }
        }

        int res = 0;
        // BFS
        while (!badOranges.empty()) {
            // auto [row, col] = badOranges.front(); badOranges.pop();
            auto badOrange = badOranges.front(); badOranges.pop();
            int row = badOrange.first, col = badOrange.second;
            // 根据方向开始遍历
            for (int i = 0; i < 4; i ++) {
                int x = row + dx[i], y = col + dy[i];
                // 更新新鲜橘子的数量，以及腐烂的时间
                if (x >= 0 && x < m && y >= 0 && y < n && badTime[x][y] == -1 && grid[x][y] != 0) {
                    badTime[x][y] = badTime[row][col] + 1;
                    badOranges.emplace(x, y);
                    if (grid[x][y] == 1) {
                        grid[x][y] = 2;
                        count --;
                        res = badTime[x][y];
                        if (count == 0) break;
                    }
                }
            }
        }

        return count == 0 ? res : -1;
    }

private:
    static const int N = 10;
    int badTime[N][N];            // 记录橘子全部腐烂需要的时间
    int count = 0;                // 记录新鲜的橘子数量
    int dx[4] = { -1, 0, 1, 0 };  // 横坐标，方向：上右下左
    int dy[4] = { 0, 1, 0, -1 };  // 纵坐标，方向：上右下左
};

int main() {
    Solution solution;
    vector<vector<int>> grid = {
        {2, 1, 1},
        {1, 1, 0},
        {0, 1, 1}
    };

    printArray(grid);
    int result = solution.orangesRotting(grid);
    cout << "Days taken for all oranges to rot: " << result << endl;
    printArray(grid);

    return 0;
}

Golang 代码

package main

import (
	"fmt"
)

// rowToString 将一行整数切片转换为带分隔符的字符串
func rowToString(row []int) string {
	result := ""
	for _, x := range row {
		result += fmt.Sprintf("%d ", x)
	}
	return result[:len(result)-1] // 去掉最后一个多余的空格
}

/*
	基本思路：
		广度优先搜索（BFS）：
			使用 BFS 模拟腐烂过程，因为腐烂是逐层扩散的，适合用 BFS 实现。
		初始化队列和计数器：
			遍历整个网格，统计新鲜橘子的数量，并将所有腐烂的橘子加入队列。
		逐层腐烂：
			每分钟处理队列中的所有腐烂橘子，将其相邻的新鲜橘子腐烂，并加入队列。
			每处理完一层，时间加1。
		检查结果：
			如果所有新鲜橘子都被腐烂，返回时间。
			如果还有新鲜橘子，返回 -1。

    时间复杂度：O(mn)
        其中 m 是网格的行数，n 是网格的列数
        每个单元格最多被访问一次，因此时间复杂度为 O(mn)。
    空间复杂度：O(mn)
        队列的大小最多为所有腐烂橘子的数量，最坏情况下为 O(mn)。
        因此，空间复杂度为 O(mn)。
*/
// orangesRotting 计算腐烂所有新鲜橘子的最小时间
func orangesRotting(grid [][]int) int {
    rows, cols := len(grid), len(grid[0])
	freshCount := 0
	badOranges := [][2]int{}

	// 初始化队列和新鲜橘子计数
	for r := 0; r < rows; r ++ {
		for c := 0; c < cols; c ++ {
			if grid[r][c] == 1 {
				freshCount ++
			} else if grid[r][c] == 2 {
				badOranges = append(badOranges, [2]int{r, c})
			}
		}
	}

	// 如果没有新鲜橘子，直接返回 0
	if freshCount == 0 {
		return 0
	}

	// BFS 遍历
	dirs := [][2]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}
	badTime := 0
	for len(badOranges) > 0 {
		n := len(badOranges)
		for i := 0; i < n; i ++ {
			badOrange := badOranges[0]
			badOranges = badOranges[1:]
            // 根据方向开始遍历
			for _, dir := range dirs {
                // 更新新鲜橘子的数量，以及腐烂的时间
				nr, nc := badOrange[0] + dir[0], badOrange[1] + dir[1]
				if nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1 {
					grid[nr][nc] = 2
					freshCount --
					badOranges = append(badOranges, [2]int{nr, nc})
				}
			}
		}
		badTime ++
	}

	// 如果还有新鲜橘子，返回 -1
	if freshCount > 0 {
		return -1
	}
	return badTime - 1 // 减去最后多加的 1
}

func main() {
	// 测试用例
	testCases := []struct {
		grid     [][]int
		expected int
	}{
		{
			grid: [][]int{
				{2, 1, 1},
				{1, 1, 0},
				{0, 1, 1},
			},
			expected: 4,
		},
		{
			grid: [][]int{
				{2, 1, 1},
				{0, 1, 1},
				{1, 0, 1},
			},
			expected: -1,
		},
		{
			grid: [][]int{
				{0,2},
			},
			expected: 0,
		},
	}

	for i, tc := range testCases {
        fmt.Printf("Test Case %d, Input: grid =\n", i+1)
		for _, row := range tc.grid {
            // 使用 rowToString 打印带分隔符的
            fmt.Printf("%s\n", rowToString(row))
		}
		result := orangesRotting(tc.grid)

        if result == tc.expected {
			fmt.Printf("Test Case %d, Output: %d, PASS\n", i+1, result)
        } else {
            fmt.Printf("Test Case %d, Output: %d, FAIL (Expected: %d)\n", i+1, result, tc.expected)		
        }
	}
}