200.

岛屿数量

中等

给你一个由'1'（陆地）和'0'（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例

1：

输入：grid
=
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
输出：1

示例

2：

输入：grid
=
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
输出：3

提示：

• m

  ==

  grid.length

• n

  ==

  grid[i].length

• 1

  <=

  300

• grid[i][j]的值为'0'或'1'

📝

核心笔记：岛屿数量

(一句话总结)

“遇到陆地1就计数，然后派出

DFS

小分队把这块连通的陆地全部踩成2，防止重复计算。

”

• DFS

  像病毒扩散：从一个源头开始，只要相邻是1就传染过去。

• 原地修改

  (In-place)：不需要额外的visited布尔数组，直接在grid上修改状态（1->2），节省了

  算法流程

  (Scan)：

• • 双重循环遍历网格。

  • 一旦遇到'1'，说明发现了一个新的岛屿。

    计数器ans++。

  • 立刻调用dfs，把这个'1'及其相连的所有'1'都感染掉。

1. 感染

   (Infect)：

• • 终止条件：越界

    (i,

    j不合法)或者不是陆地

    (grid[i][j]

    '1')。

  • 标记：grid[i][j]

    =

    '2'。

    这一步至关重要，它保证了我们不会走回头路，也不会陷入死循环。

  • 扩散：向上下左右四个方向递归。

🔍

题目：LC

利用短路逻辑：先判断越界，再判断值，防止

IndexOutOfBounds

特有)

• • StackOverflowError。

    Java

    1000x1000

    全是1），递归深度可能爆栈。

  • 解决：面试中如果被问到，可以提议用

    BFS

    Find)。

• [

  ]为什么判断条件是!=

  '1'而不是==

  '0'？

• • 这是一个好习惯。

    因为!=

    两种情况，逻辑更严密。

• [

  ]能不能不改原数组？

• • 如果面试官要求"Immutable

    Input"，你就必须开一个boolean[][]

    visited数组来记录访问状态，空间复杂度会增加。

🖼️

数字演练

Grid:

['1',
'1',
'1']

1. Loop

   (0,0):

   1。

   调用dfs。

• • (0,0)变

    '2'。

  • 向右感染(0,1)变

    '2'。

  • 向下感染(1,0)变

    '2'。

  • 连通区域全部处理完毕。

1. Loop

   '2'

   2。

   调用dfs。

• • (2,2)变

    '2'。

1. Result:

   ---