Как решать задачи на 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 const8 направлений, если разрешены диагонали:
const directions8 = [
[1, 0],
[-1, 0],
[0, 1],
[0, -1],
[1, 1],
[1, -1],
[-1, 1],
[-1, -1],
] as constDFS по 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 islands | DFS/BFS components |
| Shortest path | BFS |
| Flood fill | DFS/BFS |
| Rotten oranges | Multi-source BFS |
| Walls and gates | Multi-source BFS |
| Word search | Backtracking |
| Number of enclaves | DFS/BFS от границы |
| Pacific Atlantic water flow | DFS/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 - несколько стартовых клеток.