#include <stdlib.h>
int orangesRotting(int **grid, int gridSize, int *gridColSize) {
static const int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int rows = gridSize, cols = gridColSize[0];
// each cell is enqueued at most once, so rows * cols slots suffice
int (*q)[2] = malloc(rows * cols * sizeof *q);
int head = 0, tail = 0;
int fresh = 0;
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 2)
q[tail][0] = i, q[tail][1] = j, tail++;
else if (grid[i][j] == 1)
fresh++;
}
int minutes = 0;
while (head < tail && fresh > 0) {
int levelEnd = tail;
minutes++;
while (head < levelEnd) {
int r = q[head][0], c = q[head][1];
head++;
for (int d = 0; d < 4; d++) {
int nr = r + dirs[d][0], nc = c + dirs[d][1];
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols)
continue;
if (grid[nr][nc] != 1)
continue;
grid[nr][nc] = 2;
fresh--;
q[tail][0] = nr, q[tail][1] = nc, tail++;
}
}
}
free(q);
return fresh == 0 ? minutes : -1;
}
#include <queue>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
int orangesRotting(vector<vector<int>> &grid) {
static constexpr int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
int rows = grid.size(), cols = grid[0].size();
queue<pair<int, int>> q;
int fresh = 0;
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 2)
q.push({i, j});
else if (grid[i][j] == 1)
fresh++;
}
int minutes = 0;
while (!q.empty() && fresh > 0) {
int sz = q.size();
minutes++;
for (int k = 0; k < sz; k++) {
auto [r, c] = q.front();
q.pop();
for (auto [dr, dc] : dirs) {
int nr = r + dr, nc = c + dc;
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols)
continue;
if (grid[nr][nc] != 1)
continue;
grid[nr][nc] = 2;
fresh--;
q.push({nr, nc});
}
}
}
return fresh == 0 ? minutes : -1;
}
};
package graphs
func orangesRotting(grid [][]int) int {
dirs := [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}
rows, cols := len(grid), len(grid[0])
var q [][2]int
fresh := 0
for i := 0; i < rows; i++ {
for j := 0; j < cols; j++ {
if grid[i][j] == 2 {
q = append(q, [2]int{i, j})
} else if grid[i][j] == 1 {
fresh++
}
}
}
minutes := 0
for len(q) > 0 && fresh > 0 {
sz := len(q)
minutes++
for k := 0; k < sz; k++ {
r, c := q[0][0], q[0][1]
q = q[1:]
for _, d := range dirs {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nc < 0 || nr >= rows || nc >= cols {
continue
}
if grid[nr][nc] != 1 {
continue
}
grid[nr][nc] = 2
fresh--
q = append(q, [2]int{nr, nc})
}
}
}
if fresh == 0 {
return minutes
}
return -1
}
import java.util.ArrayDeque;
import java.util.Queue;
class Solution {
private static final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
public int orangesRotting(int[][] grid) {
int rows = grid.length, cols = grid[0].length;
Queue<int[]> q = new ArrayDeque<>();
int fresh = 0;
for (int i = 0; i < rows; i++)
for (int j = 0; j < cols; j++) {
if (grid[i][j] == 2)
q.offer(new int[] {i, j});
else if (grid[i][j] == 1)
fresh++;
}
int minutes = 0;
while (!q.isEmpty() && fresh > 0) {
int sz = q.size();
minutes++;
for (int k = 0; k < sz; k++) {
int[] cur = q.poll();
int r = cur[0], c = cur[1];
for (int[] d : DIRS) {
int nr = r + d[0], nc = c + d[1];
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols)
continue;
if (grid[nr][nc] != 1)
continue;
grid[nr][nc] = 2;
fresh--;
q.offer(new int[] {nr, nc});
}
}
}
return fresh == 0 ? minutes : -1;
}
}
const DIRS = [
[1, 0],
[0, 1],
[-1, 0],
[0, -1],
];
/**
* @param {number[][]} grid
* @return {number}
*/
var orangesRotting = function (grid) {
const rows = grid.length,
cols = grid[0].length;
let q = [];
let fresh = 0;
for (let i = 0; i < rows; i++)
for (let j = 0; j < cols; j++) {
if (grid[i][j] === 2) q.push([i, j]);
else if (grid[i][j] === 1) fresh++;
}
let minutes = 0;
while (q.length > 0 && fresh > 0) {
// swap in a fresh array per level: Array.shift() is O(n)
const next = [];
minutes++;
for (const [r, c] of q) {
for (const [dr, dc] of DIRS) {
const nr = r + dr,
nc = c + dc;
if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
if (grid[nr][nc] !== 1) continue;
grid[nr][nc] = 2;
fresh--;
next.push([nr, nc]);
}
}
q = next;
}
return fresh === 0 ? minutes : -1;
};
from collections import deque
from typing import List
DIRS = ((1, 0), (0, 1), (-1, 0), (0, -1))
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
rows, cols = len(grid), len(grid[0])
q = deque()
fresh = 0
for i in range(rows):
for j in range(cols):
if grid[i][j] == 2:
q.append((i, j))
elif grid[i][j] == 1:
fresh += 1
minutes = 0
while q and fresh > 0:
minutes += 1
for _ in range(len(q)):
r, c = q.popleft()
for dr, dc in DIRS:
nr, nc = r + dr, c + dc
if nr < 0 or nc < 0 or nr >= rows or nc >= cols:
continue
if grid[nr][nc] != 1:
continue
grid[nr][nc] = 2
fresh -= 1
q.append((nr, nc))
return minutes if fresh == 0 else -1
use std::collections::VecDeque;
const DIRS: [(isize, isize); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];
impl Solution {
pub fn oranges_rotting(mut grid: Vec<Vec<i32>>) -> i32 {
let (rows, cols) = (grid.len(), grid[0].len());
let mut q = VecDeque::new();
let mut fresh = 0;
for i in 0..rows {
for j in 0..cols {
if grid[i][j] == 2 {
q.push_back((i, j));
} else if grid[i][j] == 1 {
fresh += 1;
}
}
}
let mut minutes = 0;
while !q.is_empty() && fresh > 0 {
minutes += 1;
for _ in 0..q.len() {
let (r, c) = q.pop_front().unwrap();
for (dr, dc) in DIRS {
// wrapping_add_signed turns -1 at 0 into usize::MAX, caught by the bounds check
let (nr, nc) = (r.wrapping_add_signed(dr), c.wrapping_add_signed(dc));
if nr >= rows || nc >= cols {
continue;
}
if grid[nr][nc] != 1 {
continue;
}
grid[nr][nc] = 2;
fresh -= 1;
q.push_back((nr, nc));
}
}
}
if fresh == 0 { minutes } else { -1 }
}
}