Алгоритм Першого річка – пошук мінімального шляху в двовимірному полі

Повне пояснення

Коротке пояснення

Алгоритм Першого річка – це пошук найкоротшого шляху в двовимірному полі за допомогою BFS (Breadth‑First Search). Він розглядає усі сусідні клітинки рівномірно, тому перший знайдений шлях до цілі є найкоротшим.

Аналогія

Уявіть, що ви стоїте в центрі лабіринту і розповсюджуєте «світло» рівномірно в усі напрямки. Коли світло дотягується до цілі, це найкоротший шлях.

Коли застосовувати

• Пошук у двовимірному полі (матриці) з клітинками 0/1, де 1 – перешкода.
• Необхідно знайти мінімальну кількість кроків між двома точками.
• Клітинки можна рухати лише вгору, вниз, ліворуч і праворуч.
• Кількість клітинок невелика (до кількох тисяч) – BFS працює швидко.
• Потрібна точність, а не приблизний шлях.

Кроки алгоритму

1. Перевірити, що початкова і кінцева клітинки доступні.
2. Ініціалізувати чергу з початковою точкою і масив відвіданих.
3. Поки черга не порожня:
   • Витягнути поточну клітинку.
   • Якщо це ціль – повернути відстань.
   • Для кожного з чотирьох сусідів: перевірити межі, перешкоди і чи не відвідано.
   • Додати сусіда в чергу з оновленою відстанню.
4. Якщо ціль недоступна – повернути null або -1.

Візуальна інтуїція (текстова)

grid = [
  [0,1,0],
  [0,0,0],
  [1,0,0]
]
start = (0,0)
end   = (2,2)

BFS пошук:
(0,0) → (1,0) → (1,1) → (1,2) → (2,2)
Кількість кроків: 4

Складність

• Часова складність: O(n·m), де n – кількість рядків, m – стовпців.
• Пам’ятна складність: O(n·m) для черги і масиву відвіданих.
• У найгіршому випадку алгоритм розглядає всі клітинки.

Код (js)

// Пошук найкоротшого шляху у двовимірному полі за допомогою BFS
function bfs(grid, start, end) {
  const rows = grid.length;
  const cols = grid[0].length;

  // Перевірка коректності початкових і кінцевих точок
  const [sx, sy] = start;
  const [ex, ey] = end;
  if (grid[sx][sy] !== 0 || grid[ex][ey] !== 0) return null; // недоступна точка

  // Масив відвіданих клітинок
  const visited = Array.from({ length: rows }, () => Array(cols).fill(false));
  // Черга для BFS: кожен елемент – [x, y, distance]
  const queue = [];

  // Ініціалізуємо пошук з початкової точки
  queue.push([sx, sy, 0]);
  visited[sx][sy] = true;

  // Вектор напрямків: вниз, вверх, праворуч, ліворуч
  const directions = [[1,0], [-1,0], [0,1], [0,-1]];

  while (queue.length > 0) {
    const [x, y, dist] = queue.shift(); // витягуємо перший елемент

    if (x === ex && y === ey) return dist; // досягнуто цілі

    for (const [dx, dy] of directions) {
      const nx = x + dx;
      const ny = y + dy;

      // Перевірка меж і перешкод
      if (nx >= 0 && nx < rows && ny >= 0 && ny < cols) {
        if (!visited[nx][ny] && grid[nx][ny] === 0) {
          visited[nx][ny] = true;
          queue.push([nx, ny, dist + 1]);
        }
      }
    }
  }

  return null; // ціль недоступна
}

// Маленький тестовий приклад
const grid = [
  [0, 1, 0],
  [0, 0, 0],
  [1, 0, 0]
];
console.log(bfs(grid, [0, 0], [2, 2])); // очікуваний результат: 4

Типові помилки і поради

1. Не перевіряти, чи клітинка – перешкода: це призводить до нескінченного циклу.
2. Використовувати for...in для масивів: індекси будуть рядками, що викликає помилки.
3. Забути про відвідані клітинки: алгоритм може повторно обробляти ті ж позиції, збільшуючи час.
4. Неправильний порядок напрямків: не критично, але може вплинути на шлях у випадку декількох рішень.
5. Використання рекурсії замість черги: викликає переповнення стеку для великих полів.

Перевір себе

1. Яка складність часу має BFS у двовимірному полі?
2. Чому важливо маркувати клітинки як відвідані під час пошуку?