岛屿数量
给你一个由 ‘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
解题
1.主循环:
遍历整个矩阵,如果当前位置为’1’,则从这个位置的上下左右四个方向做深度优先遍历或者广度优先遍历(使用队列,队列元素为int [] 数组,存储行列下标),同时岛屿数量++。
2.dfs/bfs:
在遍历的时候把同一岛屿的’1’ 置’0’,避免后续其他岛屿扫描到。dfs注意终止条件/bfs判断直到队列为空
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for(int i = 0; i < grid.length; i++){
for(int j = 0; j<grid[0].length; j++){
if(grid[i][j] == '1'){
bfs(grid,i,j);
count++;
}
}
}
return count;
}
//深度优先遍历
public void dfs(char [][]grid, int i, int j){
if(i<0 || j<0 || i>grid.length-1 || j>grid[0].length-1 || grid[i][j]=='0') return;
grid[i][j] = '0';
dfs(grid,i,j+1);
dfs(grid,i,j-1);
dfs(grid,i+1,j);
dfs(grid,i-1,j);
}
//广度优先遍历
public void bfs(char[][] grid, int i, int j){
Queue<int []> queue = new LinkedList<>();
queue.add(new int[]{i,j});
while(!queue.isEmpty()){
int [] cur = queue.remove();
int m = cur[0], n = cur[1];
if(m>=0 && m<grid.length && n>=0 && n<grid[0].length && grid[i][j]=='1'){
grid[i][j] = '0';
bfs(grid,i,j+1);
bfs(grid,i,j-1);
bfs(grid,i+1,j);
bfs(grid,i-1,j);
}
}
}
}