1. Идея

Нужно найти кратчайший путь из левого верхнего угла матрицы в правый нижний, если:

• можно ходить только по клеткам со значением 0;
• двигаться можно в 8 направлениях;
• длина пути считается по количеству посещённых клеток.

Так как каждый переход из клетки в соседнюю имеет одинаковую стоимость 1, задача сводится к поиску кратчайшего пути в невзвешенном графе.
Для таких задач стандартный и оптимальный подход — поиск в ширину (BFS).

Каждая клетка матрицы — это вершина графа, а переходы в 8 соседей — рёбра.

BFS обходит вершины слоями:

• сначала все клетки на расстоянии 1,
• затем все клетки на расстоянии 2,
• потом на расстоянии 3,
• и так далее.

Поэтому первый момент, когда мы попадаем в правый нижний угол, и будет ответом.

2. Наблюдения

Наблюдение 1. Если старт или финиш заблокирован, ответа нет

Если:

• grid[0][0] == 1, или
• grid[n-1][n-1] == 1,

то путь невозможен сразу.

Наблюдение 2. Двигаться можно в 8 направлениях

Для клетки (x, y) допустимы переходы в:

• вверх,
• вниз,
• влево,
• вправо,
• и 4 диагонали.

Это удобно хранить как набор смещений:

(-1, -1), (-1, 0), (-1, 1),
( 0, -1),          ( 0, 1),
( 1, -1), ( 1, 0), ( 1, 1)

Наблюдение 3. BFS естественно считает кратчайшее расстояние

Если в очередь сначала положить стартовую клетку, а потом расширять все возможные переходы, то:

• все клетки, извлечённые раньше, имеют не большее расстояние;
• как только дошли до финиша, найденный путь минимален.

Наблюдение 4. Посещённые клетки нужно помечать сразу

Если не отмечать посещение, одна и та же клетка может много раз попасть в очередь.
Поэтому при добавлении клетки в очередь её нужно сразу пометить как посещённую.

Можно использовать:

• отдельный массив dist / used,
• или менять саму матрицу.

Во многих решениях удобно менять grid[x][y] = 1, чтобы не ходить в эту клетку повторно.

3. Алгоритм

Пусть размер матрицы n x n.

1. Если стартовая или конечная клетка заблокирована, вывести -1.
2. Создать очередь для BFS.
3. Положить в неё стартовую клетку (0, 0) с расстоянием 1.
4. Пометить старт как посещённый.
5. Пока очередь не пуста:
   • достать текущую клетку (x, y) и её расстояние d;
   • если (x, y) — это правый нижний угол, вернуть d;
   • перебрать все 8 направлений;
   • для каждого соседа (nx, ny):
     • проверить, что он внутри матрицы;
     • проверить, что grid[nx][ny] == 0;
     • пометить его посещённым;
     • добавить в очередь с расстоянием d + 1.
6. Если BFS завершился и финиш не достигнут, вывести -1.

4. Почему это работает

Докажем корректность алгоритма.

1. BFS рассматривает только допустимые пути

Мы добавляем в очередь только клетки, которые:

• находятся внутри границ матрицы;
• имеют значение 0, то есть по ним можно ходить;
• ещё не были посещены.

Значит, любая последовательность переходов, построенная алгоритмом, соответствует корректному пути по условию задачи.

2. Клетка впервые посещается по кратчайшему пути

BFS работает слоями по расстоянию от старта:

• сначала расстояние 1,
• потом 2,
• потом 3,
• и так далее.

Если клетка впервые попала в очередь с расстоянием d, то существует путь длины d до неё.
Предположим, что существует более короткий путь. Тогда эта клетка должна была бы быть достигнута на одном из предыдущих слоёв и попасть в очередь раньше. Противоречие.

Значит, первое найденное расстояние до каждой клетки — минимально возможное.

3. Первый найденный путь до финиша — кратчайший

Как только BFS извлекает из очереди клетку (n-1, n-1), её расстояние уже минимально среди всех возможных путей.
Следовательно, возвращаемое значение и есть длина кратчайшего пути.

4. Если путь существует, алгоритм его найдёт

BFS перебирает все клетки, достижимые из старта.
Если финиш достижим, он обязательно будет посещён.
Если после полного обхода достижимых клеток финиш не найден, значит, пути не существует.

Следовательно, алгоритм корректен.

5. Сложность

Пусть n — размер стороны матрицы.

Всего клеток: n^2.

Каждая клетка:

• не более одного раза попадает в очередь;
• для неё проверяется 8 соседей.

Поэтому:

• время: O(n^2)
• память: O(n^2) в худшем случае из-за очереди

Если помечать посещение прямо в grid, отдельный массив посещения не нужен, но очередь всё равно может содержать до O(n^2) клеток.

CPP

#include <iostream>
#include <vector>
#include <queue>
#include <array>

using namespace std;

int shortestPathBinaryMatrix(vector<vector<int>>& grid) {
    int n = (int)grid.size();
    if (n == 0) return -1;
    if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) return -1;

    queue<array<int, 3>> q;
    q.push({0, 0, 1});
    grid[0][0] = 1;

    const int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
    const int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1};

    while (!q.empty()) {
        auto cur = q.front();
        q.pop();

        int x = cur[0];
        int y = cur[1];
        int dist = cur[2];

        if (x == n - 1 && y == n - 1) {
            return dist;
        }

        for (int dir = 0; dir < 8; ++dir) {
            int nx = x + dx[dir];
            int ny = y + dy[dir];

            if (nx >= 0 && nx < n && ny >= 0 && ny < n && grid[nx][ny] == 0) {
                grid[nx][ny] = 1;
                q.push({nx, ny, dist + 1});
            }
        }
    }

    return -1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<vector<int>> grid(n, vector<int>(n));

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cin >> grid[i][j];
        }
    }

    cout << shortestPathBinaryMatrix(grid) << '\n';
    return 0;
}

PYTHON

from collections import deque
import sys


def shortest_path_binary_matrix(grid):
    n = len(grid)
    if n == 0:
        return -1
    if grid[0][0] != 0 or grid[n - 1][n - 1] != 0:
        return -1

    q = deque()
    q.append((0, 0, 1))
    grid[0][0] = 1

    directions = [
        (-1, -1), (-1, 0), (-1, 1),
        (0, -1),           (0, 1),
        (1, -1),  (1, 0),  (1, 1)
    ]

    while q:
        x, y, dist = q.popleft()

        if x == n - 1 and y == n - 1:
            return dist

        for dx, dy in directions:
            nx = x + dx
            ny = y + dy

            if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 0:
                grid[nx][ny] = 1
                q.append((nx, ny, dist + 1))

    return -1


def main():
    input = sys.stdin.readline
    n = int(input())
    grid = [list(map(int, input().split())) for _ in range(n)]
    print(shortest_path_binary_matrix(grid))


if __name__ == "__main__":
    main()