题解 | #岛屿数量#
岛屿数量
https://www.nowcoder.com/practice/0c9664d1554e466aa107d899418e814e
这种方法总体来说就是遍历各个格子，遇到陆地就遍历整块大陆，边遍历边标记，后续不再重复遍历。
这种方法贴近人类思想，便于理解，但是很慢。
import java.util.*;
public class Solution {
/**
* 判断岛屿数量
* @param grid char字符型二维数组
* @return int整型
*/
public void dfs(int i, int j, char[][] grid, int[][] searched){
int m = grid.length, n = grid[0].length;
Deque<Integer[]> deque = new LinkedList();
deque.addLast(new Integer[]{i,j});
searched[i][j] = 1;
while(!deque.isEmpty()){
Integer[] temp = deque.removeFirst();
int p = temp[0];
int q = temp[1];
if(p+1<m && searched[p+1][q]==0 && grid[p+1][q]=='1'){
deque.addLast(new Integer[]{p+1,q});
searched[p+1][q] = 1;
}
if(p-1>=0 && searched[p-1][q]==0 && grid[p-1][q]=='1'){
deque.addLast(new Integer[]{p-1,q});
searched[p-1][q] = 1;
}
if(q+1<n && searched[p][q+1]==0 && grid[p][q+1]=='1'){
deque.addLast(new Integer[]{p,q+1});
searched[p][q+1] = 1;
}
if(q-1>=0 && searched[p][q-1]==0 && grid[p][q-1]=='1'){
deque.addLast(new Integer[]{p,q-1});
searched[p][q-1] = 1;
}
}
}
public int solve (char[][] grid) {
// write code here
int count = 0, m = grid.length, n = grid[0].length;
int[][] searched = new int[m][n];
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j]=='1' && searched[i][j]==0){
count += 1;
dfs(i, j, grid, searched);
}
}
}
return count;
}
}
