题目描述
给定一个二维的网格图，包含1和0，分别代表陆地和水，计算其中岛屿的个数。岛屿均有水包围，并且由水平或竖直方向上的陆地连接而成。你可以假设网格的四周均被水包围。
样例
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
从任意一个陆地点开始，即可通过四连通的方式，dfs或者bfs到所有与之相连的陆地，即遍历完整个岛屿；遍历结束后将遍历过的点清0。
重复以上过程，记录起点的个数即可。
- dfs AC 代码
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
int rows,cols;
public void dfs(int x,int y,char[][]grid){
grid[x][y] = '0';
for (int i=0;i<4;i++){
int a = x + dx[i];
int b = y + dy[i];
if (a>=0&&a<rows&&b>=0&&b<cols&&grid[a][b]=='1'){
dfs(a,b,grid);
}
}
}
public int numIslands(char[][] grid) {
if (grid==null || grid.length==0 || grid[0].length==0) return 0;
rows = grid.length;
cols = grid[0].length;
int count = 0;
for (int i=0;i<rows;i++){
for (int j=0;j<cols;j++){
if (grid[i][j]=='1'){
count++;
dfs(i,j,grid);
}
}
}
return count;
}
- bfs java运行超时
int dx[] = {-1,0,1,0}, dy[] = {0,1,0,-1};
int rows,cols;
public void bfs(int x,int y,char[][]grid){
Pair<Integer,Integer> pair = new Pair<>(x,y);
Queue<Pair<Integer,Integer>> queue = new LinkedList<>();
queue.add(pair);
while (!queue.isEmpty()){
Pair<Integer,Integer> temp = queue.poll();
grid[temp.getKey()][temp.getValue()] = '0';
for (int i=0;i<4;i++){
int a = temp.getKey() + dx[i];
int b = temp.getValue() + dy[i];
if (a>=0&&a<rows&&b>=0&&b<cols&&grid[a][b]=='1'){
queue.add(new Pair<>(a,b));
}
}
}
}
public int numIslands(char[][] grid) {
if (grid==null || grid.length==0 || grid[0].length==0) return 0;
rows = grid.length;
cols = grid[0].length;
int count = 0;
for (int i=0;i<rows;i++){
for (int j=0;j<cols;j++){
if (grid[i][j]=='1'){
count++;
bfs(i,j,grid);
}
}
}
return count;
}
3.并查集做法: 将二维数组重新编号，从0开始，从左到右，从上到下，直到nm-1（其中n为行数，m为列数），对于位置(i,j)则编号为im+j，那么相邻（左右，上下）的为同一个值，则认为他们相通。那么最终只要统计一下father[i]==i且对应值为1的个数即可。
AC代码
final int maxn = 100000;
int[] parent;
int rows,cols;
int findX(int x){
while (x!=parent[x]){
x = parent[x];
}
return x;
}
void Union(int x,int y){
x = findX(x);
y = findX(y);
if (x > y){
parent[x] = y;
}else if (x < y){
parent[y] = x;
}
}
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
rows = grid.length;
cols = grid[0].length;
parent = new int[maxn];
for (int i = 0; i < maxn; i++) {
parent[i] = i;
}
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
int t1 = i * cols + j;
int t2 = t1 + 1; //右边
int t3 = t1 + cols; //下边
if (j + 1 < cols && grid[i][j] == grid[i][j + 1]) {
Union(t1, t2);
}
if (i + 1 < rows && grid[i][j] == grid[i + 1][j]) {
Union(t1, t3);
}
}
}
int count = 0;
for (int i=0;i<rows*cols;i++){
if (parent[i]==i&&grid[i/cols][i%cols]=='1'){
count++;
}
}
return count;
}
