岛屿数量
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
codeType
输入：grid = [
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出：1
示例 2：
codeType
输入：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 <= m, n <= 300
- grid[i][j] 的值为 '0' 或 '1'
解法
碰到1就进行深搜/广搜，将相连的1全部置0
ts
const dfs = (grid: string[][], y: number, x: number) => {
const h: number = grid.length
const w: number = grid[0].length
grid[y][x] = '0' // 当前访问到的节点置0
if(x - 1 >= 0 && grid[y][x - 1] === '1') dfs(grid, y, x - 1) // 左
if(x + 1 < w && grid[y][x + 1] === '1') dfs(grid, y, x + 1) // 右
if(y - 1 >= 0 && grid[y - 1][x] === '1') dfs(grid, y - 1, x) // 下
if(y + 1 < h && grid[y + 1][x] === '1') dfs(grid, y + 1, x) // 上
}
const bfs = (grid: string[][], y: number, x: number) => {
const h: number = grid.length
const w: number = grid[0].length
let q: number[][] = []
q.push([y, x])
while(q.length !== 0){
const [ curY, curX ] = q.shift()
grid[curY][curX] = '0' // 当前访问点置0
if(curX - 1 >= 0 && grid[curY][curX - 1] === '1') q.push([curY, curX - 1])
if(curX + 1 < w && grid[curY][curX + 1] === '1') q.push([curY, curX + 1])
if(curY - 1 >= 0 && grid[curY - 1][curX] === '1') q.push([curY - 1, curX])
if(curY + 1 < h && grid[curY + 1][curX] === '1') q.push([curY + 1, curX])
}
}
function numIslands(grid: string[][]): number {
// 把矩阵看作是一个无向图
// 相邻的1之间才有边
// 每找到一个1，就进行一次深度/广度遍历，并且把找到的1置0
// 进行几次深度/广度遍历就说明有几个岛屿
const h: number = grid.length
if(h <= 0 ) return 0
const w: number = grid[0].length
let res = 0
// 遍历图，碰到1就进行一次深搜/广搜
for(let i = 0; i < h; i++){
for(let j = 0; j < w; j++){
if(grid[i][j] === '1'){
// dfs(grid, i, j)
bfs(grid, i, j)
res++
}
}
}
return res
};