1. Идея

Нужно найти кратчайший путь в квадратной сетке n × n из клетки (0, 0) в клетку (n - 1, n - 1).

Разрешены переходы в 8 направлений:

• вверх, вниз, влево, вправо;
• и по четырём диагоналям.

Все переходы имеют одинаковую "стоимость": за один шаг мы переходим в соседнюю клетку. Значит, классический способ найти кратчайший путь в таком графе — это BFS (поиск в ширину).

Каждую безопасную клетку 0 будем считать вершиной графа, а переходы в соседние клетки — рёбрами. Тогда задача сводится к поиску кратчайшего пути в невзвешенном графе.

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

1. Если стартовая клетка (0, 0) непроходима, ответа нет сразу.

2. Если конечная клетка (n - 1, n - 1) непроходима, ответа тоже нет.

3. Если n = 1 и единственная клетка безопасна, путь состоит ровно из одной клетки, значит ответ 1.

4. BFS обходит клетки слоями:

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

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

5. Чтобы не заходить в одну и ту же клетку много раз, нужно помечать посещённые клетки. В эталонном решении это делается прямо в массиве grid: посещённую клетку превращают в 1.

3. Алгоритм

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

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

Докажем, что алгоритм действительно находит длину кратчайшего допустимого пути.

Почему подходит BFS

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

В нашей задаче:

• каждая безопасная клетка — вершина;
• переход в одного из 8 соседей — ребро;
• каждый переход стоит одинаково: один шаг.

Значит, BFS здесь применим напрямую.

Почему первая найденная длина — минимальная

Очередь в BFS устроена так, что сначала обрабатываются все клетки с меньшей длиной пути, а только потом с большей.

Если клетка впервые попала в очередь с длиной dist, то более короткого пути до неё уже не существует. Иначе она была бы достигнута раньше.

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

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

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

Это не только корректно, но и важно для эффективности: каждая клетка обрабатывается не более одного раза.

5. Сложность

Пусть всего n × n клеток.

• Каждая клетка может попасть в очередь не более одного раза.
• Для каждой клетки мы проверяем не более 8 соседей.

Поэтому:

• время работы: O(n^2)
• память: O(n^2)

При n <= 100 это работает очень быстро.

6. Код на C++17

#include <iostream>
#include <vector>
#include <queue>
#include <array>
using namespace std;

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];
        }
    }

    if (n == 0) {
        cout << -1 << '\n';
        return 0;
    }

    if (grid[0][0] != 0 || grid[n - 1][n - 1] != 0) {
        cout << -1 << '\n';
        return 0;
    }

    if (n == 1) {
        cout << 1 << '\n';
        return 0;
    }

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

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

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

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

        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) {
                continue;
            }
            if (grid[nx][ny] != 0) {
                continue;
            }

            if (nx == n - 1 && ny == n - 1) {
                cout << dist + 1 << '\n';
                return 0;
            }

            grid[nx][ny] = 1;
            q.push({nx, ny, dist + 1});
        }
    }

    cout << -1 << '\n';
    return 0;
}

7. Код на Python 3

import sys
from collections import deque

def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    it = iter(data)
    n = int(next(it))
    grid = [[int(next(it)) for _ in range(n)] for _ in range(n)]

    if n == 0:
        print(-1)
        return

    if grid[0][0] != 0 or grid[n - 1][n - 1] != 0:
        print(-1)
        return

    if n == 1:
        print(1)
        return

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

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

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

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

            if nx < 0 or nx >= n or ny < 0 or ny >= n:
                continue
            if grid[nx][ny] != 0:
                continue

            if nx == n - 1 and ny == n - 1:
                print(dist + 1)
                return

            grid[nx][ny] = 1
            q.append((nx, ny, dist + 1))

    print(-1)

if __name__ == "__main__":
    main()