**BFS: Уровень 2. Shortest Path (Кратчайший путь)**

Если мы читаем в условиях задачи «Найти кратчайший путь», «минимальное количество ходов», «за сколько шагов» и если каждый шаг стоит одинаково (+1), это почти всегда BFS.

### Почему здесь не работает DFS? - DFS уйдет в самую глубокую ветку слева, пройдет там до конца, вернется, упадет в следующую... это долго и не эффективно.

BFS действует иначе. Представьте таблицу `int[][] grid`, каждая клетка — это вершина графа, ребра соединяют её с соседями сверху, снизу, слева и справа, и мы двигаемся волнами.
Сначала проверяем всё на расстоянии 1 от старта, потом всё на расстоянии 2.

Идея алгоритма

1. Кладем в очередь не просто узел, а массив координат `{row, col}`.

2. Чтобы не ходить кругами, заводим массив или сет `visited` (посещенные клетки). Поставили ногу на клетку — пометили её грязной. Второй раз не наступаем.

3. Достаем позицию из очереди.

4. Смотрим на 4 соседа (вверх, вниз, влево, вправо).

5. Если сосед — стена (`#`) или уже посещен — игнорируем.

6. Если сосед — выход (`E`) — возвращаем текущую дистанцию + 1.

7. Иначе помечаем соседа как посещенный и кладем его в очередь с увеличенной дистанцией.

### Код

// Направления движения: вверх, вниз, влево, вправо
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public int findShortestPath(char[][] grid) {
if (grid == null || grid.length == 0) return -1;

int rows = grid.length;
int cols = grid[0].length;

boolean[][] visited = new boolean[rows][cols];
Queue<int[]> queue = new ArrayDeque<>();

// Ищем точку старта S
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (grid[r][c] == 'S') {
queue.offer(new int[]{r, c});
visited[r][c] = true;
}
}
}

int steps = 0;

while (!queue.isEmpty()) {
// Обрабатываем весь текущий слой целиком
int size = queue.size();

for (int i = 0; i < size; i++) {
int[] curr = queue.poll();
int row = curr[0], col = curr[1];

// Нашли выход
if (grid[row][col] == 'E') {
return steps;
}

// Проверяем соседей
for (int[] d : dirs) {
int nextRow = row + d[0];
int nextCol = col + d[1];

// Валидность: внутри границ, не стена, не были тут раньше
if (nextRow >= 0 && nextRow < rows && nextCol >= 0 && nextCol < cols) {
if (!visited[nextRow][nextCol] && grid[nextRow][nextCol] != '#') {
visited[nextRow][nextCol] = true;
queue.offer(new int[]{nextRow, nextCol});
}
}
}
}
// Закончили слой — сделали один шаг
steps++;
}

// Если очередь опустела, а E не найден
return -1;
}

Разбор кода:
* Очередь объектов vs примитивов: Здесь используется `ArrayDeque<int[]>`. Это быстро и экономит память на создании кастомных классов вроде `class Cell { int x, y; }`.
* Цикл `for (int i = 0; i < size; i++)`: Самая важная деталь для задач на шаги. Мы фиксируем размер очереди в начале итерации. Все элементы, добавленные внутрь этого цикла, попадут в обработку только на следующем шаге (`steps++`).
Без этой обертки счетчик шагов будет расти слишком быстро.
* Массив `visited`: Критически важная деталь. Без него алгоритм свалится в бесконечный цикл, гоняя одну и ту же волну по кругу между двумя пустыми клетками.

Типичные ловушки новичков
1. Забыть про границы массива. Обращение к `grid[-1][0]` выбросит `ArrayIndexOutOfBoundsException`. Всегда проверяйте `nextRow >= 0 && nextRow < rows`.
2. Пометить клетку посещенной слишком поздно. Если сначала добавить в очередь, а пометить `visited` только при извлечении (`poll`), одна и та же клетка попадет в очередь десять раз от разных родителей. Очередь раздуется, сложность ухудшится.