200 岛屿的数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1:
输入: [ [‘1’,‘1’,‘1’,‘1’,‘0’], [‘1’,‘1’,‘0’,‘1’,‘0’], [‘1’,‘1’,‘0’,‘0’,‘0’], [‘0’,‘0’,‘0’,‘0’,‘0’] ] 输出: 1 示例 2:
输入: [ [‘1’,‘1’,‘0’,‘0’,‘0’], [‘1’,‘1’,‘0’,‘0’,‘0’], [‘0’,‘0’,‘1’,‘0’,‘0’], [‘0’,‘0’,‘0’,‘1’,‘1’] ] 输出: 3 解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
思路
深度优先
class Solution {
private int d
[][]={{0,1},{1,0},{0,-1},{-1,0}};
private int n
,m
;
private boolean visited
[][];
public int numIslands(char[][] grid
){
if(grid
==null
|| grid
.length
==0 || grid
[0].length
==0){
return 0;
}
m
= grid
.length
;
n
= grid
[0].length
;
visited
=new boolean[m
][n
];
int res
= 0;
for(int i
=0;i
<m
;i
++){
for(int j
=0;j
<n
;j
++){
if(grid
[i
][j
]=='1' && !visited
[i
][j
]){
dfs(grid
,i
,j
);
res
++;
}
}
}
return res
;
}
private void dfs(char[][] grid
,int x
,int y
){
visited
[x
][y
]=true;
for(int i
=0;i
<4;i
++){
int newx
= x
+d
[i
][0];
int newy
= y
+d
[i
][1];
if(inArea(newx
,newy
) && !visited
[newx
][newy
] && grid
[newx
][newy
]=='1'){
dfs(grid
,newx
,newy
);
}
}
}
private boolean inArea(int x
,int y
){
return x
>=0 && x
<m
&& y
>=0 && y
<n
;
}
}
广度优先
private int rows
;
private int cols
;
public int numIslands(char[][] grid
) {
int[][] directions
= {{-1, 0}, {0, -1}, {1, 0}, {0, 1}};
rows
= grid
.length
;
if (rows
== 0) {
return 0;
}
cols
= grid
[0].length
;
boolean[][] marked
= new boolean[rows
][cols
];
int count
= 0;
for (int i
= 0; i
< rows
; i
++) {
for (int j
= 0; j
< cols
; j
++) {
if (!marked
[i
][j
] && grid
[i
][j
] == '1') {
count
++;
LinkedList
<Integer> queue
= new LinkedList<>();
queue
.addLast(i
* cols
+ j
);
marked
[i
][j
] = true;
while (!queue
.isEmpty()) {
int cur
= queue
.removeFirst();
int curX
= cur
/ cols
;
int curY
= cur
% cols
;
for (int k
= 0; k
< 4; k
++) {
int newX
= curX
+ directions
[k
][0];
int newY
= curY
+ directions
[k
][1];
if (inArea(newX
, newY
) && grid
[newX
][newY
] == '1' && !marked
[newX
][newY
]) {
queue
.addLast(newX
* cols
+ newY
);
marked
[newX
][newY
] = true;
}
}
}
}
}
}
return count
;
}
