Количество анклавов: задача поиска в глубину с матрицей смежности

Решение этой проблемы LeetCode для графиков

Учитесь ли вы в колледже или совершенствуете свои навыки для технических собеседований, у всех нас есть время в жизни, когда мы сталкиваемся с графиками. Графики — это удивительная структура данных для хранения сложных взаимосвязей между объектами, сущностями и даже людьми (как на Facebook!). Эта структура состоит из ребер и вершин и имеет различные способы реализации. У Geeksforgeeks есть отличный обзор графиков здесь, если вам нужно освежить в памяти.

Для целей этой статьи мы столкнемся с графами, реализованными с помощью матрицы смежности. Эта реализация использует вложенный массив и отслеживает ребра между двумя путями, используя координаты (i,j)где i и jявляются вершинами. Итак, если есть путь между i и j, значение по координате i, j будет 1, иначе будет 0.

Проблема

Сегодня мы будем вместе решать общую задачу на собеседовании, известную на LeetCode как Число анклавов:

Вам дана бинарная матрица m x n grid, где 0 представляет ячейку моря, а 1 представляет ячейку суши. Движение состоит в переходе из одной ячейки земли в другую соседнюю (в 4-х направлениях) ячейку земли или в выходе за границу grid. Возвращает количество ячеек земли в grid для которых мы не можем выйти за границу сетки ни за какое количество ходов.

Здесь матрица смежности используется для отслеживания того, есть ли между i,j, и нам нужно подсчитать всю землю. Однако есть подвох: нам нужно исключить земли, у которых есть путь к границе матрицы. Мы будем решать эту проблему, используя алгоритм поиска в глубину (DFS). Идея состоит в том, чтобы перебрать каждую ячейку в сетке и, если ячейка является землей («1»), выполнить поиск в глубину, чтобы пометить все соединенные земли как посещенные и проверить, находится ли ячейка на границе сетки. Если он не на границе, увеличьте количество островов. Легче сказать, чем сделать, я знаю..

Прежде чем мы начнем, важно понять, что такое алгоритм поиска в глубину (DFS). Этот алгоритм, по сути, полностью исследует каждый путь, прежде чем проверять следующий возможный путь из заданной начальной точки. Так, например, если у вас есть начальная точка A с путями B и C, она сначала исследует путь B и все пути B, прежде чем проверит C. Подробное объяснение этого алгоритма читайте здесь .

Решение

Без дальнейших церемоний, давайте начнем с определения количества анклавов. Во-первых, давайте перечислим все, что нам нужно проверить:

• Проверить, находится ли позиция (r, c) в границах заданного графика. Когда мы проверяем каждую координату и ее пути, нам нужно убедиться, что мы находимся на допустимой координате, поскольку мы имеем дело с матрица (которая реализована под капотом с помощью массивов/списков). Если бы у нас был вспомогательный метод, который каждый раз справлялся бы с этим за нас, это сделало бы нашу жизнь намного проще.
• Проверить, находится ли позиция (r, c) рядом с позицией за пределами. Поскольку мы ищем пути за пределами границ, нам нужно будет проверить, какая земля имеет доступ к местоположению за пределами границ. Мы создадим этот помощник, чтобы изолировать эту логику при реализации более сложного алгоритма.
• Проверить, имеет ли позиция (r, c) путь к позиции за пределами поля, просматривая все пути в четырех направлениях (вверх, вниз, влево, вправо). Этот метод будет использовать два других наших метода. вспомогательные методы с рекурсивной DFS для поиска любой связанной земли, которая имеет доступ к положению вне границ.
• Отметьте посещенные позиции, особенно для всех позиций на пути к позиции за пределами поля, посетив все пути в четырех направлениях (вверх, вниз, влево, вправо). Это будет важно, чтобы помочь нам считать только те земли, которые не находятся на пути за пределы. Мы хотим убедиться, что земли, на которых есть такие пути, не учитываются, и мы можем сделать это, отмечая их как посещенные, когда мы проходим через них.
• Повторяйте по графику, отслеживая количество земель, которые не находятся на пути к выходу за пределы.

Реализация

Ниже приведены определения функций задач/вспомогательных методов, которые мы определили выше. Позже в этой статье мы рефакторим некоторые методы из нашей первой реализации, чтобы упростить пространство и время. Однако для начала давайте сосредоточимся на том, как работает каждый отдельный шаг, чтобы полностью понять проблему и решение. Прочитайте пояснения с комментариями во фрагменте кода ниже, чтобы понять шаги.

// return true if r,c is in bounds, else false
const isInBounds = (grid, r, c) => {}

// returns true if r,c is adjacent to boundary
const canWalkOffBoundary = (grid, r, c) => {}

// return true if r,c has a path to boundary and track visited coordinates
const hasPathToBoundary = (grid, r, c, visited) => {} 

// mark all connected coordinates as visited by setting its value to 0
const floodFillDFS = (grid, r, c, color=1, newColor=0) => {}

// Number of Enclaves: calculate number of lands that don't have a path to boundary
const numEnclaves = (grid) => {} 

Мы можем начать с реализации некоторых из наших более простых методов. Вот моя реализация метода isInBoundsmethod:

// Return true if r,c is in bounds, else false
const isInBounds = (grid, r, c) => {
    // ensure our row and cols are not undefined
    if (!grid || !grid[r]) {
        return false
    }
    // ensure r is a valid row
    if (r < 0 || r > grid.length) {
        return false
    }
    // ensure c is a valid column for given row r
    if (c < 0 || c > grid[r].length) {
        return false
    }
    // if it passes all above checks, it must be a valid point
    return true
}

Вот как проверить, находится ли координата на границе:

// returns true if point r,c is adjacent to boundary
const canWalkOffBoundary = (grid, r, c) => {
    // check if r is a bordering row (first or last index)
    if (r === 0 || r === grid.length-1) {
        return true
    }
    // check if cis a bordering col of row r (first or last index)
    if (c === 0 || c === grid[r].length-1) {
        return true
    }
    // if it isn't, then it must not be on the border
    return false
}

Теперь о более интересных методах. Метод hasPathToBoundary требует, чтобы мы проверили все связанные земли с заданной координатой и вернули true, если какая-либо из связанных земель находится на границе. Здесь мы также хотим отслеживать наши посещенные точки, чтобы предотвратить бесконечный цикл.

const hasPathToBoundary = (grid, r, c, visited) => {
    // if we already visited this coordinate, exit method by returning null
    if (visited.has(`${r},${c}`)) {
        return
    }
    // add our coordinate to the visited Set
    visited.add(`${r},${c}`)
    // check if it is a valid coordinate (aka it is in bounds and it is land), 
    // else return false since we have checked all paths
    if (!isInBounds(grid, r, c) || grid[r][c] !== 1) {
        return false
    }
    // check if this coordinate can walk off boundary using our helper, if so return true
    if (canWalkOffBoundary(grid, r, c)) {
        return true
    }
    // recursively call this method to check paths on adjacent lands
    return hasPathToBoundary(grid, r+1, c, visited) || 
            hasPathToBoundary(grid, r-1, c, visited) || 
            hasPathToBoundary(grid, r, c-1, visited) || 
            hasPathToBoundary(grid, r, c+1, visited)
}

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

// mark all connected coordinates as visited by setting its value to 0
const floodFillDFS = (grid, r, c, color=1, newColor=0) => {
    // Make sure it is in bounds, it is a land, and not already visited
    if (!isInBounds(grid, r, c) || grid[r][c] !== color || grid[r][c] === newColor) {
        return 0
    }
    // set as visited by setting it to 0
    grid[r][c] = newColor
    // recursively call on all adjacent paths
    floodFillDFS(grid, r-1, c, color)
    floodFillDFS(grid, r+1, c)
    floodFillDFS(grid, r, c-1)
    floodFillDFS(grid, r, c+1)
}

Теперь, наконец, о нашем основном методе. Здесь мы пройдем все пути в наших графах, используя вложенный цикл for, поскольку наш граф настроен как список смежности.

const numEnclaves = (grid) => {
    // track number of land cells without a path to boundary
    let numInvalidCells = 0
    // loop over all rows
    for (let r = 0; r < grid.length; r++) {
        // loop over all columns in the row
        for (let c = 0; c < grid[r].length; c++) {
            // get value of current position
            const value = grid[r][c]
            // if it is land
            if (value === 1) {
                const visited = new Set()
                // check if it has a path to boundary
                const isTrue = hasPathToBoundary(grid, r, c, visited)
                if (isTrue) {
                    // if it does, mark all as visited and DON'T increment count
                    floodFillDFS(grid, r, c)
                } else {
                    // else, it is a land cell without path to boundary 
                    // so let's add to our count
                    numInvalidCells += 1
                }
            } 
        }
    }
    // return our count of land cells without path to boundary
    return numInvalidCells
};

Рефакторинг

Ух ты! Мы сделали это. Но мне кажется, что мы здесь немного дублируем работу. Когда мы проверяем путь к границе и заливаем заливку, мы дважды проходим все пути, прилегающие к точке. Есть ли способ, которым мы могли бы реорганизовать это, чтобы сделать это вместе? (Попробуйте сами!)

Да, есть! Итак, для нашего окончательного, рефакторинга и чистого решения мы будем использовать следующие определения:

// return true if r,c is in bounds, else false
const isInBounds = (grid, r, c) => {}

// returns true if r,c is adjacent to boundary
const canWalkOffBoundary = (grid, r, c) => {}

// return true if r,c has a path to boundary and track visited coordinates
// mark all connected coordinates as visited by setting its value to 0
// we will use the visited array to count visited lands if there is no path to boundary
const floodFillDFSWithCheck = (grid, r, c, visited, color=1, newColor=0) => {}

// Number of Enclaves: calculate number of lands that don't have a path to boundary
const numEnclaves = (grid) => {}

Таким образом, мы все еще можем использовать наши методы isInBounds и canWalkOffBoundary, но здесь мы рефакторим наши методы hasPathToBoundary и floodFillDFS в метод floodFillDFSWithCheck. Вот как:

// return true if r,c has a path to boundary and track visited coordinates
// mark all connected coordinates as visited by setting its value to 0
// we will use the visited array to count visited lands if there is no path to boundary
const floodFillDFSWithCheck = (grid, r, c, visited, color=1, newColor=0) => {
    // if out of bounds or not land or already checked (aka converted to newColor)
    if (!isInBounds(grid, r, c) || grid[r][c] !== color || grid[r][c] === newColor) {
        return false
    }
    // convert to new color to set visited
    grid[r][c] = newColor
    // add to visited array to help us keep count of what we changed
    // in case it is not a access to walk off boundary land
    visited.push(`${r},${c}`)
    // call each recursive call separately so we calculate each boolean result
    // we want to see if any of these paths return true for finding a boundary
    const isValid = canWalkOffBoundary(grid, r, c)
    const fill1 = floodFillDFSWithCheck(grid, r-1, c, visited)
    const fill2 = floodFillDFSWithCheck(grid, r+1, c, visited) 
    const fill3 = floodFillDFSWithCheck(grid, r, c-1, visited)
    const fill4 = floodFillDFSWithCheck(grid, r, c+1, visited)
    // here return all using the || to return true if any of these are true
    return isValid || fill1 || fill2 || fill3 || fill4
}

Теперь нам нужно реорганизовать наш метод numEnclaves, чтобы использовать эту новую реализацию:

const numEnclaves = (grid) => {
    let numInvalidCells = 0
    for (let r = 0; r < grid.length; r++) {
        for (let c = 0; c < grid[r].length; c++) {
            const value = grid[r][c]
            // if we found land
            if (value === 1) {
                // track visited points
                let visited = []
                // check if there is a path to boundary
                const isOffBounds = floodFillDFSWithCheck(grid, r, c, visited)
                // if there isn't, update our count of land without path to boundary
                // to all the lands we found and marked as visited on our DFS search
                if (!isOffBounds) {
                    numInvalidCells += visited.length
                }
            } 
        }
    }
    return numInvalidCells
};

Спасибо за прочтение!! Пожалуйста, прокомментируйте ниже, если у вас есть какие-либо вопросы или предложения по улучшению этого алгоритма.

Подпишитесь на DDIntel Здесь.

Посетите наш сайт здесь: https://www.datadriveninvestor.com

Присоединяйтесь к нашей сети здесь: https://datadriveninvestor.com/collaborate