994-腐烂的橘子

Mr.He...

🔗 链接

LeetCode-994 一道经典的DFS/BFS题。由于公司之前有组织培训及考试，这类题已经快做吐了。在此总结一下。（因为疫情和工作上的事情，很久没写总结了😪）

📋 代码1-DFS

按深度优先的方式进行感染，每走一步，腐烂值+1。完成后检查结果。最大的腐烂值-2就是需要的时间。如果过程中遇到了腐烂值>当前腐烂值+1的场景，则把大的腐烂值更新为当前腐烂值+1。这样才是这个橘子感染的最短时间。

class Solution {
    int time = 0;
    // 这2个数组用做上下左右4个方向。
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int xx = 0;
    int yy = 0;
    
    public int orangesRotting(int[][] grid) {
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                // 遍历格子，如果是2（烂橘子），进入dfs进行递归传染。
                if (grid[i][j] == 2) {
                    dfs(grid, i, j, 2);
                }
            }
        }

        // 传染完毕。检查结果。即grid[x][y]的最大值。另外，如果此时还有1，说明还存在未腐烂的橘子。返回-1。
        for(int i = 0; i < grid.length; i++) {
            for(int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 1) return -1;
                if (grid[i][j] > time) {
                    time = grid[i][j];
                }
            }
        }
        // time为最大的腐烂值。如果是10，说明从烂橘子（2）感染到它需要8秒。因此需要减去2。
        return time-2 <0?0:time-2;
    }

    /**
     * @param grid 输入的格子
     * @param i 横坐标
     * @param j 纵坐标
     * @param k 当前的腐烂值。初始传来的是2
     */
    private void dfs(int[][] grid, int i, int j, int k) {
        grid[i][j] = k;
        
        for (int d = 0; d < 4; d++) {
            xx = i + dx[d];
            yy = j + dy[d];
            //开始传染。条件是：
            //1.新坐标还在格子里面
            //2.即将传染的橘子是好橘子（值为1），或腐烂值>=当前橘子的腐烂值。
            // 为什么要加上上条的最后一个条件呢？举个例子。如果即将传染的橘子腐烂值是4，说明另一条路径，经过4分钟后感染了橘子；而当前这条路径3分钟即可感染橘子，那肯定是以小的为准。
            if (xx >=0 && xx < grid.length && yy >=0 && yy < grid[0].length && (grid[xx][yy] == 1 || grid[xx][yy] > k+1)) {
                dfs(grid, xx, yy, k+1);
            }
        }
    }
}

📋 代码2-BFS

按“层”进行感染。在同一时间被感染的橘子为一层。最后的最大层数就是需要的时间。

class Other {
	int time;
	int x, y;
	int xx, yy;
	int R, C;
	int code;	// 保存处理后的x.y
	int[] dx = {0,0,1,-1};
	int[] dy = {1,-1,0,0};
	
	Queue<Integer> queue = new LinkedList<Integer>();
	Map<Integer, Integer> depth = new HashMap<Integer, Integer>();
	
	public int orangesRotting(int[][] grid) {
		R = grid.length;
		C = grid[0].length;
		
		for(int i = 0; i < R; i++) {
			for(int j = 0; j < C; j++) {
				if (grid[i][j] == 2) {
					// i和j的最大值是10, 这里把j存到code的2个低位，i存到code的高位。
					code = i * 100 + j;
					queue.add(code);
					// 这个code代表的格子的感染时间为0。
					depth.put(code, 0);
				}
			}
		}
		
		while (!queue.isEmpty()) {
			int code = queue.remove();
			x = code / 100;
			y = code % 100;

			for (int d = 0; d < 4; d++) {
				xx = x + dx[d];
				yy = y + dy[d];
				// 如果下一个格子在范围内，而且是新鲜橘子
				if (0 <= xx && xx < R && 0 <= yy && yy < C && grid[xx][yy] == 1) {
					// 就进行感染，把值置为2
					grid[xx][yy] = 2;
					// 服用code变量，保存新格子的坐标。新格子，即上面说的下一层。
					int ncode = xx * 100 + yy;
					queue.add(ncode);
					// 新格子（下一层）的腐烂时间，是感染它的那个格子的时间+1
					depth.put(ncode, depth.get(code) + 1);
					// time保存当前的最大时间
					time = depth.get(ncode);
				}
			}
		}
		
		// 到这里，time里存的就是最大时间。但还需要判断是否存在新鲜橘子。如果存在，则返回-1。
		for (int[] row: grid) {
			for (int v: row) {
				if (v == 1)
					return -1;
			}
		}
		return time;
	}
}