re:re:actable
Урок 115 минут чтения

Как решать задачи на matrix и grid?

На этой странице
Кратко

Matrix/grid задачи - это задачи на двумерный массив. Их часто решают через координаты row/col, проверку границ, направления движения и BFS/DFS по соседям.

Вопрос

Как решать задачи на матрицы и сетки?

Что такое matrix/grid

Matrix - двумерный массив:

const grid = [
  [1, 1, 0],
  [0, 1, 0],
  [1, 0, 1],
]

Координаты:

grid[row][col]

Количество строк:

const rows = grid.length

Количество колонок:

const cols = grid[0]?.length ?? 0

Проверка границ

function inBounds(row: number, col: number, rows: number, cols: number): boolean {
  return row >= 0 && row < rows && col >= 0 && col < cols
}

Это одна из самых важных функций для grid задач.

Направления

4 направления:

const directions = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1],
] as const

8 направлений, если разрешены диагонали:

const directions8 = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1],
  [1, 1],
  [1, -1],
  [-1, 1],
  [-1, -1],
] as const

DFS по grid

Задача: посчитать количество островов, где 1 - земля, 0 - вода.

function numIslands(grid: string[][]): number {
  const rows = grid.length
  const cols = grid[0]?.length ?? 0
  let count = 0
 
  function dfs(row: number, col: number): void {
    if (
      row < 0 ||
      row >= rows ||
      col < 0 ||
      col >= cols ||
      grid[row][col] !== "1"
    ) {
      return
    }
 
    grid[row][col] = "0"
 
    dfs(row + 1, col)
    dfs(row - 1, col)
    dfs(row, col + 1)
    dfs(row, col - 1)
  }
 
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === "1") {
        count++
        dfs(row, col)
      }
    }
  }
 
  return count
}

Идея:

  • нашли новую землю;
  • это новый остров;
  • DFS "затапливает" весь остров, чтобы не считать его повторно.

BFS по grid

BFS удобен для shortest path по клеткам.

function shortestPath(grid: number[][]): number {
  const rows = grid.length
  const cols = grid[0]?.length ?? 0
 
  if (rows === 0 || cols === 0 || grid[0][0] === 1) {
    return -1
  }
 
  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ] as const
 
  const queue: Array<[number, number, number]> = [[0, 0, 0]]
  let head = 0
  grid[0][0] = 1
 
  while (head < queue.length) {
    const [row, col, distance] = queue[head++]
 
    if (row === rows - 1 && col === cols - 1) {
      return distance
    }
 
    for (const [dr, dc] of directions) {
      const nextRow = row + dr
      const nextCol = col + dc
 
      if (
        nextRow >= 0 &&
        nextRow < rows &&
        nextCol >= 0 &&
        nextCol < cols &&
        grid[nextRow][nextCol] === 0
      ) {
        grid[nextRow][nextCol] = 1
        queue.push([nextRow, nextCol, distance + 1])
      }
    }
  }
 
  return -1
}

Почему BFS:

первый раз дошли до клетки = минимальная дистанция

если все шаги имеют одинаковую стоимость.

visited: менять grid или отдельный Set

Вариант 1: менять grid.

Плюсы:

  • меньше памяти;
  • проще код.

Минусы:

  • мутируем input;
  • нельзя, если задача запрещает менять matrix.

Вариант 2: отдельный visited.

const visited = new Set<string>()
const key = `${row}:${col}`

Или boolean matrix:

const visited = Array.from({ length: rows }, () =>
  new Array(cols).fill(false),
)

Частые grid-паттерны

ЗадачаПодход
Count islandsDFS/BFS components
Shortest pathBFS
Flood fillDFS/BFS
Rotten orangesMulti-source BFS
Walls and gatesMulti-source BFS
Word searchBacktracking
Number of enclavesDFS/BFS от границы
Pacific Atlantic water flowDFS/BFS от океанов

Сложность

Если R - строки, C - колонки:

Time: O(R * C)
Space: O(R * C)

Почему: каждая клетка обычно посещается максимум один раз.

Что важно помнить: частые ошибки

  • Путать row и col.
  • Не обработать пустой grid.
  • Проверять grid[0].length, когда grid пустой.
  • Забыть visited и уйти в цикл.
  • Использовать DFS с глубокой рекурсией и получить call stack overflow.
  • Использовать BFS, но shift() вместо head.
  • Забыть, что диагонали обычно не считаются соседями, если задача не сказала обратное.

Что отвечать на собеседовании?

Matrix/grid задачи я свожу к координатам row/col, проверке границ и набору направлений. Для connected components использую DFS/BFS, для shortest path с равными весами - BFS, для задач от нескольких источников - multi-source BFS. Сложность обычно O(rows * cols), потому что каждая клетка посещается не более одного раза.

Мини-шпаргалка

  • grid[row][col].
  • rows = grid.length.
  • cols = grid[0]?.length ?? 0.
  • Проверяй границы.
  • 4 directions - вверх/вниз/влево/вправо.
  • DFS - острова/flood fill.
  • BFS - shortest path.
  • Multi-source BFS - несколько стартовых клеток.

Документация

LeetCode: Matrix problems.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам