обнаружение, если есть путь от вершины к указанному c элементу в 2-мерном массиве

Question

У меня есть двумерный массив, я хочу проверить, есть ли какой-либо путь от верхней строки к указанному c элементу в массиве.

Этот способ означает: что постоянно подключен 1 сверху вниз к элементу.

Я реализовал функцию для ее решения: я могу проверять каждую строку, начиная с строки 1 , если эти 2 строки связаны, зарегистрируйте их точки подключения и продолжайте, иначе верните false (никак).

Например, первые 3 строки, соединенные этими 3 точками.

Моя JS Реализация:

function isWay(arr, row, col) {
  let count =crate_Nd_Array(arr.length);

  if (arr[row][col] == 0) {
      return false;
  }

  if (arr[row][col] == 1) {
     for(let i=1; i<arr.length; i++){
        for(let j=0; j<=col; j++){
           if(isOpen(arr,i,j)){  //is open check if the element is 1 or 0
             if(is_2_rows_connected(arr, i , j)){
  //is_2_rows_connected checks if there is a way between each 2 stacked rows.
                  let countt = count[i-1];
                  countt.push([[i,j], [i-1, j]])
             };
           }
        }
     }
  }

   return count;
}

/**is_2_rows_connected checks if there is a way between every 2 stacked rows. */

function is_2_rows_connected(arr, r, c)
{
  if(isOpen(arr,r,c) && isOpen(arr, r-1, c ))
  {   //isopen returns if T if 1 or 0
         return true;
  }

  return false;
}

Теперь я могу получить точки соединения между всеми сложенными рядами, но я застрял здесь.

Это можно решить с помощью алгоритма union-find, но я не знаю, как его инициализировать. любая помощь, пожалуйста ??

Answer 1

Вы можете начать с позиции целевой ячейки и сделать стандартный проход BFS / DFS, чтобы посетить все доступные ячейки в сетке. Если вы достигнете верхней строки во время этого возврата true и если в этом конце не будет достигнут ни один элемент верхней строки, вернитесь false.

Другой способ сделать это - начать с верхней строки. Для этого сначала добавьте все ячейки верхней строки с 1 в очередь / стек. Оттуда проверьте, достижима ли целевая ячейка, используя стандартные BFS / DFS.