Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

In fact, many algorithms are not divorced from reality, many image processing problems will use graph algorithm. The following is a map problem to share, which is to calculate the number of islands in the ocean on the map. We abstract the map into a grid and divide the map into small areas through the grid. Each small area represents a land or an ocean.

  • Where yellow is island
  • Blue is the ocean

The problem is finding the number of islands on the map.

const grid = [
    ['W'.'L'.'W'.'W'.'W'],
    ['W'.'L'.'W'.'W'.'W'],
    ['W'.'W'.'W'.'L'.'W'],
    ['W'.'W'.'L'.'L'.'W'],
    ['L'.'W'.'W'.'L'.'L'],
    ['L'.'L'.'W'.'W'.'W']]Copy the code

Used to represent a two-dimensional matrix, each cell corresponds to a coordinate (row, column).

The basic idea

Train of thought is very important, there is a train of thought that is to find the answer direction, as long as the direction is correct how to go to the end, just how much time the problem.

It is mainly to traverse all the cells, and the position of each cell can be determined by the number of rows and columns, and we can distinguish different cells by the position. Starting from the top left corner of each line of a pointer, when encountered pointer island, then traverse the adjacent cell, its adjacent unit is the unit of land, check whether the unit has been, if after the return false to skip directly, if there is no unit, traverse is, also is the depth-first traversal, All land units that can communicate with the land are traversed and marked as visited.

Iterate through all the cells

for(let r = 0; r < grid.length; r +=1) {for(let c = 0; c < grid[0].length; c +=1) {if(explore(grid,r,c,visited) === true){
            count +=1}}}Copy the code

Iterate through all the cells

Sets traversal boundaries

const rowInbounds = 0 <= r && r < grid.length;
const columnInbounds = 0 <= c && c < grid[0].length;
if(! rowInbounds || ! columnInbounds)return false
Copy the code

Sets the boundary for the walk pointer, but the pointer moves within the map. You can also control the range of pointer movement by traversing its adjacent units below, but the control is more elegant at the beginning.

Marks passing cells

const pos = r +', ' + c;
if(visited.has(pos)) return false;
visited.add(pos);
Copy the code

To mark passing cells, we can use a Set to store passing cells. The cell can be [r,c], so that the Set is not consistent.

The complete code

/** * r = # rows * c = # cols * Time:O(r c) * Space: O(rc) */

const grid = [
    ['W'.'L'.'W'.'W'.'W'],
    ['W'.'L'.'W'.'W'.'W'],
    ['W'.'W'.'W'.'L'.'W'],
    ['W'.'W'.'L'.'L'.'W'],
    ['L'.'W'.'W'.'L'.'L'],
    ['L'.'L'.'W'.'W'.'W']]const islandCount = (grid) = >{
    let count = 0
    const visited = new Set(a);for(let r = 0; r < grid.length; r +=1) {for(let c = 0; c < grid[0].length; c +=1) {if(explore(grid,r,c,visited) === true){
                count +=1}}}return count
}

const explore = (grid,r,c,visited) = > {
    const rowInbounds = 0 <= r && r < grid.length;
    const columnInbounds = 0 <= c && c < grid[0].length;
    if(! rowInbounds || ! columnInbounds)return false

    if(grid[r][c] === 'W') return false;


    const pos = r +', ' + c;
    if(visited.has(pos)) return false;
    visited.add(pos);

    explore(grid,r -1, c,visited);
    explore(grid,r +1, c,visited);
    explore(grid,r, c-1,visited);
    explore(grid,r, c+1,visited);


    return true;
}



const res = islandCount(grid);
console.log(res)

Copy the code