題目：994. Rotting Oranges

連結：https://leetcode.com/problems/rotting-oranges/description/

• 等級：Medium

解題思路

1. 建立一個已存取的網格來儲存單元格的狀態（新鮮、腐爛或空）。
2. 初始化一個序列，存放爛橙子，統計新鮮橙子的數量。
3. 檢查是否沒有新鮮橙子，返回0，如果沒有爛橙子，返回-1。
4. 當隊列不為空時循環，儲存隊列的大小。循環遍歷佇列的大小。
5. 取得隊列的最前面的儲存格。
6. 檢查牢房的四個方向，看看是否有新鮮的橘子。
7. 如果有新鮮橙子，則將其狀態更改為腐爛並減少新鮮橙子的數量，並將單元推入隊列。
8. 增加分鐘數。如果沒有新鮮橙子，則返回分鐘數。如果還有新鮮橙子，則返回-1。

class Solution {
    public int orangesRotting(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int[][] visited = grid;
        Queue<int[]> q = new LinkedList<>();
        int countFreshOrange = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j] == 2) {
                    q.offer(new int[] {i, j});
                }
                if (visited[i][j] == 1) {
                    countFreshOrange++;
                }
            }
        }
        if (countFreshOrange == 0)
            return 0;
        if (q.isEmpty())
            return -1;
        
        int minutes = -1;
        int[][] dirs = {{1, 0},{-1, 0},{0, -1},{0, 1}};
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) {
                int[] cell = q.poll();
                int x = cell[0];
                int y = cell[1];
                for (int[] dir : dirs) {
                    int i = x + dir[0];
                    int j = y + dir[1];
                    if (i >= 0 && i < m && j >= 0 && j < n && visited[i][j] == 1) {
                        visited[i][j] = 2;
                        countFreshOrange--;
                        q.offer(new int[] {i, j});
                    }
                }
            }
            minutes++;
        }
        
        if (countFreshOrange == 0)
            return minutes;
        return -1;
    }
}

• Time complexity: O(m*n)
• Space complexity: O(m*n)

題目：1091. Shortest Path in Binary Matrix

連結：https://leetcode.com/problems/shortest-path-in-binary-matrix/description/

• 等級：Medium

class Solution {
    public int shortestPathBinaryMatrix(int[][] grid) {
        int d1[] = {0,-1,-1,-1,0,1,1,1};
        int d2[] = {-1,-1,0,1,1,1,0,-1};

        if(grid[0][0] == 1){
            return -1;
        }

        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{0, 0});

        int dist = 0;
        while(!q.isEmpty()){
            int size = q.size();

            for(int i = 0; i< size;i++){
                int temp []= q.poll();

                int row = temp[0];
                int col = temp[1];

                if(row == grid.length-1 && col == grid[0].length-1){
                    return dist + 1;
                }

                for(int dir = 0;dir < 8;dir++){
                    int next_row = row+ d1[dir];
                    int next_col = col + d2[dir];

                    if(next_row < 0 || next_col < 0 || next_row >= grid.length || next_col >= grid[0].length || grid[next_row][next_col] == 1){
                        continue;
                    }

                    q.add(new int[]{next_row, next_col});
                    grid[next_row][next_col] = 1;
                }
            }
            dist++;
        }

        return -1;
    }
}

• Time complexity: O(n^2)
• Space complexity: O(n^2)