---
title: "Поиск слова в матрице (DFS/backtracking по сетке)"
url: https://algopath.pro/ru/patterns/matrix-word-search
language: ru
summary: "Ищите в сетке, шагая в соседа и потом возвращаясь обратно. Клетка помечена ровно столько времени, сколько вы внутри неё."
updated: 2026-08-24
---

# Поиск слова в матрице (DFS/backtracking по сетке)

Ищите в сетке, шагая в соседа и потом возвращаясь обратно. Клетка помечена ровно столько времени, сколько вы внутри неё.

## Поиск слова в матрице (DFS/backtracking по сетке): как это работает?

Слово может начинаться в любой клетке. Пробуйте поиск из каждой.

В клетке сравните её с текущим символом. Несовпадение сразу обрывает эту ветку.

Пометьте клетку использованной до шага дальше. Иначе путь пройдёт сам по себе.

Попробуйте по очереди всех четырёх соседей. Слово может продолжиться через любого.

Снимите пометку после возврата всех четырёх вызовов. Следующий поиск обязан увидеть клетку свободной.

Дойти до конца слова значит найти его. Ниже этой точки ничего не важно.

- `старт в A, индекс 0` Сетка это A, B над C, D, а слово это ABD.
- `сосед B, индекс 1` B совпадает со второй буквой, поэтому тоже помечается.
- `из B: A помечена` Именно пометка не даёт пути повернуть назад.
- `D, индекс 2` D совпадает с последней буквой. Слово собрано.
- `ответ = истина` Помечены были две клетки, и обе очищаются на выходе.

## Поиск слова в матрице (DFS/backtracking по сетке): когда применять?

- существует ли слово как путь по доске
- проследить буквы через соседние клетки без повторов
- DFS с возвратом (backtracking) по сетке
- пометить клетку посещённой, затем отменить пометку

## Поиск слова в матрице (DFS/backtracking по сетке): с чем путают?

- **Бэктрекинг** - Это бэктрекинг, где деревом служит сетка. Вариантами служат четыре соседа.
- **Обход графа BFS / DFS** - Обход помечает клетку раз и навсегда. Здесь пометка снимается на выходе.
- **Компоненты связности** - Заливка тоже ходит по соседям, но пометки не снимает. Она считает, а не ищет.
- **Trie (префиксное дерево)** - Когда слов много, trie обрезает обход. Без него каждое слово стоит своего поиска.

## Поиск слова в матрице (DFS/backtracking по сетке): сложность по времени и памяти

Сетка r на c и слово длины L стоят O(rc умножить на 4^L). Работает это за счёт обрезки.

## Поиск слова в матрице (DFS/backtracking по сетке): разбор примера

### Найти все слова, спрятанные в сетке

Даны сетка букв и список слов. Верните все слова, которые есть в сетке.

Поиск каждого слова по отдельности повторяет огромный объём работы.

Сначала сложите все слова в trie.

Потом пройдите сетку один раз, неся узел trie вместо индекса в слове. Отсутствующий потомок обрезает ветку.

```javascript
function findWords(board, words) {
    const root = { children: {} };
    for (const word of words) {
        let node = root;
        for (const c of word) {
            node.children[c] = node.children[c] ?? { children: {} };
            node = node.children[c];
        }
        node.word = word;
    }

    const found = [];

    function walk(r, c, node) {
        const letter = board[r]?.[c];
        const next = letter && node.children[letter];
        if (!next) return; // no word continues this way

        if (next.word) {
            found.push(next.word);
            next.word = null; // never report the same word twice
        }

        board[r][c] = "#"; // marked only while we are inside this cell
        walk(r + 1, c, next);
        walk(r - 1, c, next);
        walk(r, c + 1, next);
        walk(r, c - 1, next);
        board[r][c] = letter;
    }

    for (let r = 0; r < board.length; r++) {
        for (let c = 0; c < board[0].length; c++) walk(r, c, root);
    }

    return found;
}
```

## Поиск слова в матрице (DFS/backtracking по сетке): частые ошибки

- **Забывают снять пометку** Клетка остаётся закрытой для всех последующих поисков. Восстанавливайте её после четырёх вызовов.
- **Помечают настоящей буквой** Метка, которая встречается в словах, позволяет пути пройти клетку заново. Возьмите символ вне алфавита.
- **Проверяют границы после чтения** Чтение вне сетки падает или даёт undefined. Проверяйте координаты до обращения.
- **Ищут каждое слово отдельно** Сто слов означают сто полных обходов. Один trie сводит их к единственному обходу.

## Поиск слова в матрице (DFS/backtracking по сетке): задачи с собеседований

- **Поиск слова в сетке** Одно слово, четыре соседа на каждом шаге.
- **Поиск слов в сетке II** Trie обрезает обход, когда слов много.
- **Число островов** Тот же обход, только пометки не снимаются.
- **Путь с наибольшим золотом** Соберите значение и верните его на выходе.
- **Уникальные пути III** Каждую свободную клетку надо посетить ровно один раз.
- **Крыса в лабиринте** Та же форма, но записывается сам путь.
- **Решатель судоку** Сетка, где вариантами служат цифры, а не направления.

## JavaScript

```javascript
function exist(board, word) {
    const rows = board.length, cols = board[0].length;
    function dfs(r, c, i) {
        if (i === word.length) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[i]) return false;
        const tmp = board[r][c];
        board[r][c] = "#";
        const found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) ||
                      dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
        board[r][c] = tmp;
        return found;
    }
    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
}
```

## Python

```python
def exist(board, word):
    rows, cols = len(board), len(board[0])

    def dfs(r, c, i):
        if i == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != word[i]:
            return False
        tmp, board[r][c] = board[r][c], "#"
        found = (dfs(r + 1, c, i + 1) or dfs(r - 1, c, i + 1) or
                 dfs(r, c + 1, i + 1) or dfs(r, c - 1, i + 1))
        board[r][c] = tmp
        return found

    return any(dfs(r, c, 0) for r in range(rows) for c in range(cols))
```

## PHP

```php
function exist(array &$board, string $word): bool {
    $rows = count($board); $cols = count($board[0]);
    $dfs = function (int $r, int $c, int $i) use (&$board, &$dfs, $word, $rows, $cols): bool {
        if ($i === strlen($word)) return true;
        if ($r < 0 || $r >= $rows || $c < 0 || $c >= $cols || $board[$r][$c] !== $word[$i]) return false;
        $tmp = $board[$r][$c];
        $board[$r][$c] = "#";
        $found = $dfs($r + 1, $c, $i + 1) || $dfs($r - 1, $c, $i + 1)
              || $dfs($r, $c + 1, $i + 1) || $dfs($r, $c - 1, $i + 1);
        $board[$r][$c] = $tmp;
        return $found;
    };
    for ($r = 0; $r < $rows; $r++) {
        for ($c = 0; $c < $cols; $c++) {
            if ($dfs($r, $c, 0)) return true;
        }
    }
    return false;
}
```