Problem: 994. 腐烂的橘子

思路

👨‍🏫 参考

复杂度

时间复杂度: $O(n)$

空间复杂度: $O(n)$

💝 Code

class Solution {
	int[] dx = new int[] { 0, 1, 0, -1 };// 行 矢量坐标数组 
	int[] dy = new int[] { 1, 0, -1, 0 };// 列 矢量坐标数组 

	/**
	 * @param grid 0表示格子为空，1 表示新鲜橘子，2 表示腐烂橘子
	 * @return
	 */
	public int orangesRotting(int[][] grid)
	{
		int n = grid.length;
		if (n == 0)
			return 0;
		int m = grid[0].length;
		Queue<int[]> q = new LinkedList<>();// 当前的腐烂橘子
		int cnt = 0;// 当前新鲜橘子数
		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
			{
				if (grid[i][j] == 1)
					cnt++;
				else if (grid[i][j] == 2)
				{
					q.add(new int[] { i, j });// 坏橘子入队
				}
			}
		int round = 0;// 表示腐烂的轮数（分钟数）
		while (cnt > 0 && !q.isEmpty())//当新鲜橘子为 0 或者 坏橘子把能感染的都感染了 退出循环
		{
			round++;
			int size = q.size();
//			当前队列里边前size项，就是当前这一分钟（轮）存在的坏橘子
			for (int i = 0; i < size; i++)
			{
				int[] orange = q.poll();
				int x = orange[0];
				int y = orange[1];
				for (int j = 0; j < 4; j++)
				{
					int xx = x + dx[j];
					int yy = y + dy[j];
					// BFS搜索 上下左右 的橘子（主义防止越界）
					if (xx >= 0 && xx < n && yy >= 0 && yy < m && grid[xx][yy] == 1)
					{
						grid[xx][yy] = 2;// 污染当前新鲜橘子
						q.add(new int[] { xx, yy });// 坏橘子上车
						cnt--;// 存活的新鲜橘子 - 1
					}
				}
			}
		}
		if (cnt > 0)//还剩有新鲜橘子，说明躲在死角了
			return -1;
		else
			return round;
	}
}