题目描述
给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
求岛屿数量，本质上是求那些1是相连的。这样我们至少需要先把矩阵中已有的点全部看完，也就是把整个矩阵全部遍历一遍，在遍历的方式中，我们可以选择深度优先遍历或者广度优先遍历。
在遍历的过程中，我们把遍历到的1，改写成其他的数字或字符，以达到占位的目的，防止下次遍历到他的时候重复计算进去岛屿的数量，同时也在遍历的过程中记录下岛屿数量的情况。
方法一：深度优先遍历
解题思路
深度优先就是一条路走到头的一个过程，先从一个数值为1的点开始，在分别遍历他的上下左右四个方向，在同一个方向上就一直往下找，比如，上方向是1，就当前点改写成其他的字符，再遍历到上方向，此时，再往他的上下左右四个方向进行判断，如果上方向还是1，就先改写当前点，再仍然遍历到上方向，依次类推即可。
实现的这个过程最常用的方式就是使用递归栈来一层一层压进去。
这个过程用文字、用代码表诉都比较绕，直观一点的理解就看看下边的图示吧，再结合着代码带入例子跟着走一遍流程，这样会比较好理解一些。
代码示例
import java.util.*;
public class Solution {
/**
* 记录岛屿的数量
*/
private int num = 0;
/**
* 判断岛屿数量
* @param grid char字符型二维数组
* @return int整型
*/
public int solve (char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return -1;
}
int rows = grid.length;
int cols = grid[0].length;
// 挨个遍历每个点
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 只有当前点为 1， 才有可能是一个岛屿。
if (grid[i][j] == '1') {
// 遍历到的点置为 ‘#’
grid[i][j] = '#';
// 以这个点辐射出去看这个岛屿的最大范围是多少
dfs(grid, i, j);
// 以 （i，j） 为原点，向外辐射出去，有 1 个岛屿存在
num++;
}
}
}
return num;
}
/**
* 深度优先遍历， 以 （x，y） 为原点，看在 grid 矩形里，有多少个 ‘1’ 和原点相连组成一个岛屿；
* 相连的那些 ‘1’ 置为 ‘#’，是为了不妨碍下次遍历到这个点时的操作，为了不重复计算相同的岛屿
* @param grid 整个大矩形
* @param x 原点的横坐标
* @param y 原点的纵坐标
*/
public void dfs(char[][] grid, int x, int y) {
int rows = grid.length;
int cols = grid[0].length;
// 看原点和其相连的上方是否能组成岛屿
if (isValid(x - 1, y, rows, cols) && grid[x - 1][y] == '1') {
grid[x - 1][y] = '#';
// 以相连的上方为原点，接着看周围是否能组成岛屿
dfs(grid, x - 1, y);
}
// 看原点和其右边是否能组成岛屿
if (isValid(x, y + 1, rows, cols) && grid[x][y + 1] == '1') {
grid[x][y + 1] = '#';
// 以相连的右边为原点，接着看周围是否能组成岛屿
dfs(grid, x, y + 1);
}
// 看原点和其相连的下方是否能组成岛屿
if (isValid(x + 1, y, rows, cols) && grid[x + 1][y] == '1') {
grid[x + 1][y] = '#';
// 以相连的下方为原点，接着看周围是否能组成岛屿
dfs(grid, x + 1, y);
}
// 看原点和其左边是否能组成岛屿
if (isValid(x, y - 1, rows, cols) && grid[x][y - 1] == '1') {
grid[x][y - 1] = '#';
// 以相连的左边为原点，接着看周围是否能组成岛屿
dfs(grid, x, y - 1);
}
}
/**
* 判断 （x，y） 点是否在 整个大矩形的范围内
* @param x 当前点的横坐标
* @param y 当前点的纵坐标
* @param rows 整个大矩形的 行数
* @param cols 整个大矩形的 列数
* @return 如果在范围内，返回true； 否在返回false
*/
public boolean isValid(int x, int y, int rows, int cols) {
return x >= 0 && x < rows && y >= 0 && y < cols;
}
} 复杂度分析
时间复杂度：O(M*N)
M 为矩阵的行数，N 为矩阵的列数。
首先需要遍历整个矩阵，这里是个双重 for 循环，时间复杂度已经到 O(M*N) 了。
在循环里面还有个 dfs 的递归操作，这里因为是一个矩阵存储元素，可以根据下标直接找到对应的点，所以这里面主要是一个空间的开销，时间上的开销主要是在整个双重循环遍历的过程中。即便有在 dfs 操作中遍历到的点，也会因为遍历到的原因，他的数值改变不会为 1，之后再遍历到他的时候不会再进行相应的 dfs 操作。
所以，最后总的时间复杂度为：O(M*N)
空间复杂度：O(M*N)
M 为矩阵的行数，N 为矩阵的列数。
空间上的开销主要就是在 dfs 中递归栈的开辟上，在极端情况下，就比如整个矩阵中所有的数字都是 1 ，这时需要将每个点都在同一个 dfs 递归中压栈进去。
所以，空间复杂度为 O(M*N)
方法二：广度优先遍历
解题思路
广度优先就是先从一个点出发，再向上下左右四个方向扩散，先不慌着在一个方向扩散下去，先把这四个方向都扩散完，扩散完了在依次往这些扩散到的点再来从上下左右四个方向扩散出去，也就是一圈一圈的扩散出去，知道不能扩了或者扩到边界了就停止。
实现这个过程最常用的方式就是使用队列的方式来一层一层地存储这些点，然后再来拿出来向四周扩散。
操作流程见下列图示和代码。
代码示例
import java.util.*;
public class Solution {
/**
* 判断岛屿数量
* @param grid char字符型二维数组
* @return int整型
*/
public int solve (char[][] grid) {
if (grid == null || grid.length == 0 || grid[0].length == 0) {
return -1;
}
int rows = grid.length;
int cols = grid[0].length;
// 记录岛屿的数量
int nums = 0;
Queue<String> queue = new LinkedList<>();
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
// 以当前 (i, j) 向四周扩散， 找到一个岛屿
if (grid[i][j] == '1') {
// 遍历到的点置为 ‘#’ , 防止下次重复计算
grid[i][j] = '#';
// 将该点加入到队列中，以便之后拿出来，以他为原点，向四周扩散，计算岛屿
queue.add(i + "!" + j);
while (!queue.isEmpty()) {
// 从队列中拿出来的点
String[] split = queue.poll().split("!");
int x = Integer.parseInt(split[0]);
int y = Integer.parseInt(split[1]);
// 看拿出来的点的上方
if (isValid(x - 1, y, rows, cols) && grid[x - 1][y] == '1') {
grid[x - 1][y] = '#';
queue.add((x - 1) + "!" + y);
}
// 看拿出来的点的右边
if (isValid(x, y + 1, rows, cols) && grid[x][y + 1] == '1') {
grid[x][y + 1] = '#';
queue.add(x + "!" + (y + 1));
}
// 看拿出来的点的下方
if (isValid(x + 1, y, rows, cols) && grid[x + 1][y] == '1') {
grid[x + 1][y] = '#';
queue.add((x + 1) + "!" + y);
}
// 看拿出来的点的左边
if (isValid(x, y - 1, rows, cols) && grid[x][y - 1] == '1') {
grid[x][y - 1] = '#';
queue.add(x + "!" + (y - 1));
}
}
// 以点 (i,j) 向四周扩散出了 1 个岛屿
nums++;
}
}
}
return nums;
}
/**
* 判断 （x，y） 点是否在 整个大矩形的范围内
* @param x 当前点的横坐标
* @param y 当前点的纵坐标
* @param rows 整个大矩形的 行数
* @param cols 整个大矩形的 列数
* @return 如果在范围内，返回true； 否在返回false
*/
public boolean isValid(int x, int y, int rows, int cols) {
return x >= 0 && x < rows & y >= 0 && y < cols;
}
} 复杂度分析
时间复杂度：O(M*N)
M 为矩阵的行数，N 为矩阵的列数。
首先仍然是需要遍历整个矩阵，这里仍然是用一个双重 for 循环来进行遍历，到这里时间复杂度就已经为 O(M*N) 了。
在遍历的过程中，还有一个判断队列是否为空的循环，这里的时间消耗就和队列的长度有关，
空间复杂度：O( min(M, N) )
M 为矩阵的行数，N 为矩阵的列数。
在极端情况下，整个矩阵中所有的数值都是 1，这在遍历的过程中，会一直往队列里面压元素，最长可以压到 min(M, N) 的长度。
京公网安备 11010502036488号