200 Number of Islands
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.
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
遍历到是陆地的点，计数，将其转为海洋，对其相邻的点进行递归（深度或广度优先搜索）
deepth first search 版本，比较快
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') {
remove(grid, i, j);
count++;
}
}
}
return count;
}
private void remove(char[][] grid, int i, int j){
grid[i][j]='0';
if(i+1<grid.length && grid[i+1][j]=='1') remove(grid, i+1, j);
if(i-1>=0 && grid[i-1][j]=='1') remove(grid, i-1, j);
if(j+1<grid[0].length && grid[i][j+1]=='1') remove(grid, i, j+1);
if(j-1>=0 && grid[i][j-1]=='1') remove(grid, i, j-1);
}
}
broadth first search 版本，要慢一些
class Solution {
public int numIslands(char[][] grid) {
if(grid==null || grid.length==0 || grid[0].length==0) return 0;
int height=grid.length;
int width=grid[0].length;
int count=0;
for(int i=0;i<height;++i){
for(int j=0;j<width;++j){
if(grid[i][j]=='1'){
count++;
Queue<int[]> queue=new LinkedList<>();
queue.add(new int[]{i,j});
grid[i][j]='0';
bfs(grid,queue);
}
}
}
return count;
}
private void bfs(char[][] grid, Queue<int[]> queue){
while(!queue.isEmpty()){
int size = queue.size();
for(int k=0;k<size;++k){
int[] arr=queue.poll();
int i=arr[0];
int j=arr[1];
if(i-1>=0 && grid[i-1][j]=='1'){
queue.add(new int[]{i-1,j});
grid[i-1][j]='0';
}
if(j-1>=0 && grid[i][j-1]=='1') {
queue.add(new int[]{i,j-1});
grid[i][j-1]='0';
}
if(i+1<grid.length && grid[i+1][j]=='1') {
queue.add(new int[]{i+1,j});
grid[i+1][j]='0';
}
if(j+1<grid[i].length && grid[i][j+1]=='1') {
queue.add(new int[]{i,j+1});
grid[i][j+1]='0';
}
}
}
}
}