286. Walls and gates

#include <limits.h>
#include <stdlib.h>

static const int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

void islandsAndTreasure(int **grid, int gridSize, int *gridColSize) {
  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;

  for (int i = 0; i < rows; i++)
    for (int j = 0; j < cols; j++)
      if (grid[i][j] == 0)
        q[tail][0] = i, q[tail][1] = j, tail++;

  while (head < tail) {
    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] != INT_MAX)
        continue;

      grid[nr][nc] = grid[r][c] + 1;
      q[tail][0] = nr, q[tail][1] = nc, tail++;
    }
  }

  free(q);
}

#include <climits>
#include <queue>
#include <utility>
#include <vector>

using namespace std;

class Solution {
public:
  void islandsAndTreasure(vector<vector<int>> &grid) {
    rows = grid.size();
    cols = grid[0].size();
    queue<pair<int, int>> q;

    for (int i = 0; i < rows; i++)
      for (int j = 0; j < cols; j++)
        if (grid[i][j] == 0)
          q.push({i, j});

    while (!q.empty()) {
      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] != INT_MAX)
          continue;

        grid[nr][nc] = grid[r][c] + 1;
        q.push({nr, nc});
      }
    }
  }

private:
  int rows, cols;
  static constexpr int dirs[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
};

package graphs

import "math"

var dirs = [4][2]int{{1, 0}, {0, 1}, {-1, 0}, {0, -1}}

func islandsAndTreasure(grid [][]int) {
    rows, cols := len(grid), len(grid[0])
    var q [][2]int

    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if grid[i][j] == 0 {
                q = append(q, [2]int{i, j})
            }
        }
    }

    for len(q) > 0 {
        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] != math.MaxInt32 {
                continue
            }

            grid[nr][nc] = grid[r][c] + 1
            q = append(q, [2]int{nr, nc})
        }
    }
}

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    private static final int[][] DIRS = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

    public void islandsAndTreasure(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        Queue<int[]> q = new ArrayDeque<>();

        for (int i = 0; i < rows; i++)
            for (int j = 0; j < cols; j++)
                if (grid[i][j] == 0)
                    q.offer(new int[] {i, j});

        while (!q.isEmpty()) {
            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] != Integer.MAX_VALUE)
                    continue;

                grid[nr][nc] = grid[r][c] + 1;
                q.offer(new int[] {nr, nc});
            }
        }
    }
}

const INF = 2147483647;
const DIRS = [
  [1, 0],
  [0, 1],
  [-1, 0],
  [0, -1],
];

/**
 * @param {number[][]} grid
 */
var islandsAndTreasure = function (grid) {
  const rows = grid.length,
    cols = grid[0].length;
  const q = [];

  for (let i = 0; i < rows; i++)
    for (let j = 0; j < cols; j++) if (grid[i][j] === 0) q.push([i, j]);

  // index-based queue: Array.shift() is O(n)
  for (let head = 0; head < q.length; head++) {
    const [r, c] = q[head];
    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] !== INF) continue;

      grid[nr][nc] = grid[r][c] + 1;
      q.push([nr, nc]);
    }
  }
};

from collections import deque
from typing import List

INF = 2147483647
DIRS = ((1, 0), (0, 1), (-1, 0), (0, -1))


class Solution:
    def islandsAndTreasure(self, grid: List[List[int]]) -> None:
        rows, cols = len(grid), len(grid[0])
        q = deque((i, j) for i in range(rows) for j in range(cols) if grid[i][j] == 0)

        while 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] != INF:
                    continue

                grid[nr][nc] = grid[r][c] + 1
                q.append((nr, nc))

use std::collections::VecDeque;

const DIRS: [(isize, isize); 4] = [(1, 0), (0, 1), (-1, 0), (0, -1)];

impl Solution {
    pub fn islands_and_treasure(grid: &mut Vec<Vec<i32>>) {
        let (rows, cols) = (grid.len(), grid[0].len());
        let mut q = VecDeque::new();

        for i in 0..rows {
            for j in 0..cols {
                if grid[i][j] == 0 {
                    q.push_back((i, j));
                }
            }
        }

        while let Some((r, c)) = q.pop_front() {
            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] != i32::MAX {
                    continue;
                }

                grid[nr][nc] = grid[r][c] + 1;
                q.push_back((nr, nc));
            }
        }
    }
}