# 994.Rotting-Oranges

## ้ข็ฎๅฐๅ

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

## ้ข็ฎๆ่ฟฐ

In a given grid, each cell can have one of three values:

the value 0 representing an empty cell;
the value 1 representing a fresh orange;
the value 2 representing a rotten orange.
Every minute, any fresh orange that is adjacent (4-directionally) to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange.  If this is impossible, return -1 instead.

Example 1:
Input: [[2,1,1],[1,1,0],[0,1,1]]
Output: 4

## ไปฃ็ 

class Solution {
int[] dr = new int[]{-1, 0, 1, 0};
int[] dc = new int[]{0, -1, 0, 1};

public int orangesRotting(int[][] grid) {
int R = grid.length, C = grid[0].length;

Queue<Integer> queue = new ArrayDeque();
Map<Integer, Integer> depth = new HashMap();
for (int r = 0; r < R; r++) {
for (int c = 0; c < C; c++) {
if (grid[r][c] == 2) {
int code = r * C + c;
depth.put(code, 0);
}
}
}

int ans = 0;
while (!queue.isEmpty()) {
int code = queue.remove();
int r = code / C, c = code % C;
for (int k = 0; k < 4; k++) {
int nr = r + dr[k];
int nc = c + dc[k];
if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {
grid[nr][nc] = 2;
int ncode = nr * C + nc;
depth.put(ncode, depth.get(code) + 1);
ans = depth.get(ncode);
}
}
}

for (int[] row : grid) {
for (int v : row) {
if (v == 1) {
return -1;
}
}
}

return ans;
}
}

Last updated