Использование указателей и графа BFS, методов DFS для обхода 2D-матрицы

Обзор

Многие программные головоломки, такие как лабиринт, потребуют обхода каждого элемента 2D-матрицы. В двумерной матрице [ROW,COL] мы обычно посещаем каждый элемент с помощью вложенного цикла for, что занимает O(ROW*COL) времени, а иногда и O( ROW*COL), если мы храним/кешируем некоторую информацию по пути обхода.

For row = 0 to ROW:
  For col = 0 to COL: 
      Matrix[row][col]

В этой статье мы рассмотрим, как мы можем объединить обход 2D-матрицы с некоторыми трюками, чтобы решить некоторые проблемы типа лабиринта/графа в Leetcode.

Ключевой прием

Для любой 2D-матрицы, помимо знания основного вложенного цикла, ключевой прием заключается в направленных векторах в 2D-измерении с осью x и ось Y.

Допустим, если мы находимся в позиции (1,1) в виде зеленого круга, мы можем двигаться влево, вправо, вверх или вниз, как показано на рисунке ниже.

Обобщая это, если мы находимся в (x, y), мы можем либо перейти к (x + 1, y), (x-1, y), (x, y + 1) или (x, y-1) . Следовательно, мы можем иметь вектор направлений, как показано ниже:

directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];

Спиральная матрица

Учитывая m x n matrix, вернуть все элементы matrix в порядке спирали.

Источник: Литкод

С этой проблемой, очевидно, мы не можем перемещаться по 2D-матрице в обычном порядке вложенного цикла слева направо, строка за строкой. Мы должны придумать способ прохождения по спирали, который включает 4 направления, как показано ниже.

top = 0, bottom = ROW
left = 0, right = COL
if(direction==1) {
   for i = left to right: 
       //Fix row, move col
       Matrix[top][i]
   //remove the entire top row after traversing
   top++;
}
else if(direction==2) {
   for i = top to bottom: 
       //Fix col, move row
       Matrix[i][right]
   //remove the entire right col after traversing
   right--;
}
else if(direction==3) {
   for i = right to left: 
       //Fix row, move col
       Matrix[bottom][i]
   //remove the entire bottom row after traversing
   bottom--;
}
else if(direction==4) {
   for i = bottom to top: 
       //Fix col, move row
       Matrix[i][left]
   //remove the entire left col after traversing
   left++;
}

С 4 направлениями/указателями, описанными выше. Мы можем легко пройти по двумерной матрице в спиральном порядке, чередуя d1, d2, d3 и d4. У нас может быть реализация в JavaScript, как показано ниже. Примечание. Эту реализацию можно легко перевести на любой другой язык программирования.

Общая временная сложность будет O(ROW*COL), поскольку ROW и COL являются размерами матрицы. Придется посетить каждый элемент матрицы хотя бы по одному. Кроме того, пространственная сложность равна O(ROW*COL), так как нам нужно создать массив для хранения конечного результата, который включает общее количество элементов во входной матрице.

Количество островов

Дана двухмерная двоичная сетка m x n grid, которая представляет собой карту '1's (суша) и '0's (вода), возвращает количество островов.

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

Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1
Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Источник: Литкод

Поскольку остров формируется только путем соединения «1» по горизонтали или вертикали, мы можем проверить, является ли какая-либо сетка[i][j] «1». Если это так, мы можем выполнить поиск в ширину или обход графа поиска вглубь из этой позиции, чтобы увидеть, являются ли соседние позиции также «1» или частью этого острова. Мы используем счетчик островов в качестве вывода и увеличиваем его каждый раз, когда обнаруживаем новый остров. Мы можем создать высокоуровневые списки дел ниже и преобразовать высокоуровневые идеи в программную реализацию.

1. A counter variable to keep track of number of islands.
2. Iterate each position in the matrix => a nested loop
3. If see a position as "1", explore adjacent positions by bfs/dfs. If the adjacencies are also "1", it's part of the island, do not increase the counter => a bfs/dfs function
4. Keep track of the visited positions to avoid duplicate work=> a set to keep track of visited positions.

Как показано на рисунке ниже, желтая ячейка — это ячейка/позиция, которую мы посетим с помощью обычного вложенного цикла для обхода матрицы. Зеленые ячейки будут посещены поиском в ширину того, что в желтой ячейке. Красные стрелки показывают направления поиска в ширину. Очевидно, что мы будем считать новый остров каждый раз, когда увидим новую «1» в позиции, которая не была отмечена как посещенная при поиске в ширину из предыдущей «1» на последней итерации.

Мы можем реализовать подход BFS в JavaScript, как показано ниже.

Когда мы видим вложенный цикл и внутренний цикл while для поиска в ширину, мы можем подумать о O(ROW.COL)² или около того для временной сложности. Однако на самом деле мы не посещаем позицию, если она уже была посещена. Поэтому мы посещаем каждую позицию только одну, что означает, что общая временная сложность равна общему количеству элементов из ввода: O(ROW.COL). Пространственная сложность также будет O(ROW.COL), так как нам нужно хранить посещенные позиции и увеличивать некоторые элементы для очереди поиска в ширину.

Обратите внимание, что мы можем изменить этот подход поиска в ширину (BFS) на поиск в глубину (DFS), изменив только одну строку кода в строке 29. Вместо того, чтобы брать первый элемент из очереди, мы всегда можем взять последний элемент. обнаружены из очереди для глубокого поиска.

const currPos = queue.pop(); //for DFS

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

Я надеюсь, что после прочтения этой статьи вы легко поймете и справитесь с любыми задачами, связанными с обходом 2D-матрицы/лабиринта :)