1. Идея

Нужно найти минимальное число ходов от клетки S до клетки F в прямоугольной сетке, где можно ходить только вверх, вниз, влево и вправо, а через # проходить нельзя.

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

Мы будем запускать BFS из клетки S и постепенно находить расстояния до всех достижимых клеток. Когда обход закончится, ответом будет расстояние до клетки F. Если она так и осталась недостижимой, выводим -1.

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

1. Сетку удобно воспринимать как граф:

   • каждая клетка — это вершина;
   • из клетки есть рёбра в соседние по стороне клетки;
   • в стены # ходить нельзя, значит такие клетки просто не участвуют в переходах.

2. Все переходы равны по стоимости, поэтому BFS действительно находит кратчайшее расстояние по числу ходов.

3. Чтобы не посещать одну и ту же клетку много раз, удобно хранить массив dist:

   • dist[i][j] = -1, если клетка ещё не посещалась;
   • иначе там хранится минимальное число шагов от S.

4. Как только мы впервые попали в клетку, расстояние до неё уже минимально. Это ключевое свойство BFS.

3. Алгоритм

1. Считываем n и m, затем саму сетку.
2. Находим координаты стартовой клетки S и финишной клетки F.
3. Создаём массив dist размера n x m, заполняем его значением -1.
4. Помещаем стартовую клетку в очередь и записываем dist[sx][sy] = 0.
5. Пока очередь не пуста:
   • достаём текущую клетку;
   • перебираем 4 соседние клетки;
   • для каждой соседней клетки проверяем:
     • не вышли ли за границы;
     • не стена ли это;
     • не посещали ли мы её раньше;
   • если все проверки пройдены, записываем расстояние dist[nx][ny] = dist[x][y] + 1 и добавляем клетку в очередь.
6. После завершения BFS выводим dist[fx][fy].

Если путь есть, там будет минимальное число шагов. Если пути нет, там останется -1.

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

BFS обходит граф слоями:

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

В этой задаче один переход всегда увеличивает длину пути ровно на 1. Поэтому, когда BFS впервые доходит до клетки, он делает это по кратчайшему пути.

Значит:

• dist[sx][sy] = 0 — верно;
• если из клетки с правильным расстоянием d мы переходим в соседнюю непосещённую клетку, то ей присваивается d + 1;
• поскольку BFS обрабатывает клетки в порядке неубывания расстояния, более короткого пути к этой соседней клетке уже быть не может.

Следовательно, после завершения обхода значение dist[fx][fy] равно минимальному числу ходов от S до F, а если добраться нельзя, то оно остаётся -1.

5. Сложность

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

• Каждую клетку мы посещаем не более одного раза.
• Из каждой клетки проверяем не более 4 соседей.

Итоговая сложность:

• по времени: O(n * m)
• по памяти: O(n * m)

Это укладывается в ограничения задачи.

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>
#include <queue>

using namespace std;

int main() {
    int n, m;
    cin >> n >> m;

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

    int sx = -1, sy = -1;
    int fx = -1, fy = -1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == 'S') {
                sx = i;
                sy = j;
            } else if (grid[i][j] == 'F') {
                fx = i;
                fy = j;
            }
        }
    }

    vector<vector<int>> dist(n, vector<int>(m, -1));
    queue<pair<int, int>> q;

    dist[sx][sy] = 0;
    q.push({sx, sy});

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

    while (!q.empty()) {
        pair<int, int> cur = q.front();
        q.pop();

        int x = cur.first;
        int y = cur.second;

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

            if (nx < 0 || nx >= n || ny < 0 || ny >= m) {
                continue;
            }
            if (grid[nx][ny] == '#') {
                continue;
            }
            if (dist[nx][ny] != -1) {
                continue;
            }

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

    cout << dist[fx][fy] << '\n';
    return 0;
}

7. Код на Python 3

n, m = map(int, input().split())
grid = [input().strip() for _ in range(n)]

sx = sy = -1
fx = fy = -1

for i in range(n):
    for j in range(m):
        if grid[i][j] == 'S':
            sx, sy = i, j
        elif grid[i][j] == 'F':
            fx, fy = i, j

dist = [[-1] * m for _ in range(n)]
q = [(sx, sy)]
head = 0
dist[sx][sy] = 0

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

while head < len(q):
    x, y = q[head]
    head += 1

    for k in range(4):
        nx = x + dx[k]
        ny = y + dy[k]

        if nx < 0 or nx >= n or ny < 0 or ny >= m:
            continue
        if grid[nx][ny] == '#':
            continue
        if dist[nx][ny] != -1:
            continue

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

print(dist[fx][fy])