# 994. Rotting Oranges

<https://leetcode.com/problems/rotting-oranges/>

思路跟 1162 差不多,  只是要注意一些條件

和 fresh 的橘子的個數會影響到結果,&#x20;

還有要看清楚 題目的 “例子”

![](/files/-MCMtR48PYsBrcs3puDe)

ex2這樣會是 -1, ex3 會是 0

O(nm), O(nm)

![](/files/-MCMt0xYur3Pl34uf_4-)

```java
class Solution {
    int dirs[][] = {{0,1}, {0,-1}, {1,0}, {-1, 0}};
    public int orangesRotting(int[][] grid) {
        int m = grid.length; //height
        if (m == 0) {
            return -1;
        }
        int n = grid[0].length; //width
        
        int freshCount = 0;
        Queue<int[]> q = new ArrayDeque<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2) {
                    q.offer(new int[]{i, j}); //rotten (x,y) add to q first
                } else if (grid[i][j] == 1) { // count fresh
                    freshCount++;
                }
            }
        }
        if (freshCount == 0) { //ex3的情況
            return 0;
        }
        
        int count = -1;
        while (!q.isEmpty()) {
            count++;
            int levels = q.size();

            for (int i = 0; i < levels; i++) {
                int rotten[] = q.poll();
                int r = rotten[0];
                int c = rotten[1];
                
                for (int d[] : dirs) {
                    int r0 = r + d[0];
                    int c0 = c + d[1];
                    if (inArea(r0, c0, grid) && grid[r0][c0] == 1) {
                        grid[r0][c0] = 2;
                        q.offer(new int[]{r0, c0}); // 加入新的 rotten
                        freshCount--;
                    }
                }
            }
        }
        return freshCount == 0 ? count : -1; // -1: ex2的情況
    }
    
    private boolean inArea(int r, int c, int[][] grid) {
        return (r >= 0 && r < grid.length && c >=0 && c < grid[0].length);
    }
}
```

#### 2021/9/04 version

```java
/*
0 - no oranges
1 - fresh
2 - rotten

use BFS, 

add rotten to queue
count fresh one's count

if a cell has rotten, make it's neightbor cell (if it's fresh) become rotten (like spread disease), fresh--


*/
class Solution {
    private static final int DIRECTIONS[][] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
    
    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        
        int freshCount = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    queue.add(new int[]{i,j});
                }
                if (grid[i][j] == 1) {
                    freshCount++;
                }
            }
        }
        
        if (freshCount == 0) return 0;
        
        int result = -1; // why?
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int cell[] = queue.poll();
                int x = cell[0];
                int y = cell[1];
                
                for (int[] direction : DIRECTIONS) {
                    int newX = x + direction[0];
                    int newY = y + direction[1];
                    if (inArea(grid, newX, newY) && grid[newX][newY] == 1) {
                        grid[newX][newY] = 2; // makes it rotten
                        queue.add(new int[]{newX, newY});
                        freshCount--;
                    }
                }
            }
            result++; 
        }
        
        return freshCount == 0 ? result : -1;
    }
    
    private boolean inArea(int grid[][], int x, int y) {
        return (x >= 0 && x < grid.length && y >= 0 && y < grid[0].length);
    }
}


```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/dfs-and-bfs/bfs/994.-rotting-oranges.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.