[dfs]Islandの200番

質問する

Given an m x n 2D binary grid grid which represents a map of '1' s (land) and '0' s (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
m xn 2次元バイナリgridは、「1」(陸地)と「0」(水)の地図を表す場合、島の数を返します.
島は水で囲まれ、隣接する陸地を水平または垂直に接続することによって形成される.gridの4辺が水に囲まれていると仮定できます.

例

Example 1:

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

Example 2:

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

拘束

m == grid.length

n == grid[i].length

1 <= m, n <= 300

grid[i][j] is '0' or '1' .

コード#コード#

const numIslands = (grid) => {
    const m = grid.length
    const n = grid[0].length
    let res = 0;

    const dfs = (x, y) => {
        if (x < 0 || x > m - 1 || y < 0 || y > n - 1) return
        
        if (grid[x][y] === '1') {
            grid[x][y] = 'visited';
            
            dfs(x - 1, y);
            dfs(x, y - 1);
            dfs(x + 1, y);
            dfs(x, y + 1);
            return true;
        }
        return false
    }
    
    [...Array(m).keys()].forEach(i => {
         [...Array(n).keys()].forEach(j => {
             if (dfs(i, j) === true) res += 1
         })
    })
    
    return res;
};

に答える

特定のノードにアクセスする場合、ノードが'1'である場合、アクセス処理が行われ(visited)、ノードの上下、左、右にアクセスする.
最初のアクセスが成功した場合はtrueを返し、アクセスが失敗した場合はfalseを返します.

誤ったインデックスであれば、すぐに終了します.

最初のアクセスが成功すれば、周囲のすべてのアクセス可能な場所にアクセスし、アクセス処理を行うことができる.

のすべてのノードを参照し、最初のアクセスが成功したときに計算します.