题目描述
在给定的 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.lengthn == grid[i].length1 <= m, n <= 10grid[i][j]仅为0、1或2
DFS解法
使用深度优先搜索（DFS）来解决这个问题是不太直观的，因为DFS通常用于探索或搜索路径问题，例如在迷宫中寻找路径，而这个问题更适合用BFS来模拟橘子腐烂的过程。然而，如果非要用DFS，我们需要稍微改变问题的解决方式。
在DFS的情境下，我们可以对每个新鲜橘子（值为1的单元格）应用DFS，来找出它被腐烂的最短时间。在这个过程中，我们会遇到两个主要问题：
- 重复计算：相同的新鲜橘子可能会被多次计算。
- 无法保证最优解：DFS无法保证在每一步都选择最快的腐烂路径。
下面是使用DFS解决这个问题的Java代码。请注意，这种方法可能不如BFS那样高效和直观，而且可能在某些情况下无法找到最优解。
public class Solution {public int orangesRotting(int[][] grid) {int rows = grid.length;int cols = grid[0].length;int maxTime = 0; // 记录所有橘子腐烂所需的最大时间// 遍历网格中的每个单元格for (int r = 0; r < rows; r++) {for (int c = 0; c < cols; c++) {// 对于每个新鲜橘子，使用DFS来找出其腐烂所需的最短时间if (grid[r][c] == 1) {int time = dfs(grid, r, c, rows, cols);// 如果某个橘子无法腐烂，则返回-1if (time == Integer.MAX_VALUE) {return -1;}// 更新所有橘子腐烂所需的最大时间maxTime = Math.max(maxTime, time);}}}return maxTime;}private int dfs(int[][] grid, int r, int c, int rows, int cols) {// 检查边界条件和空单元格if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] == 0) {return Integer.MAX_VALUE;}// 如果找到腐烂的橘子，返回0，因为它不需要额外时间来腐烂if (grid[r][c] == 2) {return 0;}// 临时将当前单元格标记为0，以避免重复访问grid[r][c] = 0;// 递归地探索四个方向int left = dfs(grid, r, c - 1, rows, cols);int right = dfs(grid, r, c + 1, rows, cols);int up = dfs(grid, r - 1, c, rows, cols);int down = dfs(grid, r + 1, c, rows, cols);// 恢复当前单元格的值grid[r][c] = 1;// 找出四个方向上的最小腐烂时间int minTime = Math.min(Math.min(left, right), Math.min(up, down));// 返回最小时间加1（表示当前橘子腐烂所需的总时间）// 如果四周都不能腐烂，则返回最大值return minTime == Integer.MAX_VALUE ? minTime : minTime + 1;}
}
BFS解法
class Solution {public int orangesRotting(int[][] grid) {int rows = grid.length, cols = grid[0].length;Queue<int[]> queue = new LinkedList<>();int freshCount = 0;// 初始化队列，计算新鲜橘子的数量for (int r = 0; r < rows; r++) {for (int c = 0; c < cols; c++) {if (grid[r][c] == 2) {queue.offer(new int[]{r, c});} else if (grid[r][c] == 1) {freshCount++;}}}int minutesPassed = 0;int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; // 四个方向// BFSwhile (!queue.isEmpty() && freshCount > 0) {minutesPassed++;int size = queue.size();for (int i = 0; i < size; i++) {int[] point = queue.poll();int x = point[0], y = point[1];for (int[] d : directions) {int nx = x + d[0], ny = y + d[1];if (0 <= nx && nx < rows && 0 <= ny && ny < cols && grid[nx][ny] == 1) {grid[nx][ny] = 2;freshCount--;queue.offer(new int[]{nx, ny});}}}}return freshCount == 0 ? minutesPassed : -1;}
}问题拓展
51. N 皇后
用回溯加dfs解决下面这道问题，每一行有且只有一个皇后，按这种思路写dfs代码并且反复回溯校验 。
/*** 在n×n格的国际象棋上摆n个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法*/
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;class Solution {List<List<String>> result = new ArrayList<>();char[][] board;public List<List<String>> solveNQueens(int n) {board = new char[n][n];for (char[] row : board) {Arrays.fill(row, '.'); // 初始化棋盘，全部填充为 '.'}dfs(0, n);return result;}public void dfs(int row, int n) {if (row == n) {// 所有皇后都放置好了，转换棋盘为结果格式并添加到结果列表中result.add(boardToList());return;}for (int col = 0; col < n; col++) {if (isValid(row, col, n)) {board[row][col] = 'Q'; // 放置皇后dfs(row + 1, n); // 递归到下一行board[row][col] = '.'; // 回溯，撤销皇后}}}private boolean isValid(int row, int col, int n) {// 检查列for (int i = 0; i < row; i++) {if (board[i][col] == 'Q') {return false;}}// 检查左上对角线for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {if (board[i][j] == 'Q') {return false;}}// 检查右上对角线for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {if (board[i][j] == 'Q') {return false;}}return true;}private List<String> boardToList() {List<String> list = new ArrayList<>();for (char[] row : board) {list.add(new String(row));}return list;}
}
相关文章
团灭LeetCode跳跃游戏(相关话题:贪心,BFS)_跳跃游戏is bfs-CSDN博客
算法模板（二）（相关话题：广度优先搜索BFS）_bfs的搜索代价有哪些可能性-CSDN博客
LeetCode695之岛屿的最大面积（相关话题：深度优先，广度优先）_着色法问题 广度优先求小岛面积-CSDN博客
LeetCode之团灭字典序相关题目_leetcode 字典序 题-CSDN博客
LeetCode037之解数独（相关话题：回溯法）-CSDN博客
算法模板（三）（相关话题：回溯算法）_回溯算法三个模板-CSDN博客
LeetCode207之课程表(相关话题：图的遍历，拓扑排序)_visited[s]路=路true;-CSDN博客
