DFS深度优先搜索
DFS就是沿着一条路径一直走下去,当遇到终止条件的时候才会返回
遍历数组中的每一个值,如果是1就说明是岛屿,然后把它置为0或者其他的字符都可以,只要不是1就行,然后再遍历他的上下左右4个位置。如果是1,说明这两个岛屿是连着的,只能算是一个岛屿,我们还要把它置为0,然后再以它为中心遍历他的上下左右4个位置……。如果是0,就说明不是岛屿,就不在往他的上下左右4个位置遍历了。
import java.util.*; public class Solution { /** * 判断岛屿数量 * @param grid char字符型二维数组 * @return int整型 */ public int solve(char[][] grid) { //边界条件判断 if (grid == null || grid.length == 0) return 0; //统计岛屿的个数 int count = 0; //两个for循环遍历每一个格子 for (int i = 0; i < grid.length; i++) for (int j = 0; j < grid[0].length; j++) { //只有当前格子是1才开始计算 if (grid[i][j] == '1') { //如果当前格子是1,岛屿的数量加1 count++; //然后通过dfs把当前格子的上下左右4 //个位置为1的都要置为0,因为他们是连着 //一起的算一个岛屿, dfs(grid, i, j); } } //最后返回岛屿的数量 return count; } //这个方***把当前格子以及他邻近的为1的格子都会置为1 public void dfs(char[][] grid, int i, int j) { //边界条件判断,不能越界 if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return; //把当前格子置为0,然后再从他的上下左右4个方向继续遍历 grid[i][j] = '0'; dfs(grid, i - 1, j);//上 dfs(grid, i + 1, j);//下 dfs(grid, i, j + 1);//左 dfs(grid, i, j - 1);//右 } }
BFS广度优先搜索
BFS就是先把当前位置附近的访问一遍,然后再把放大继续访问
import java.util.*; public class Solution { /** * 判断岛屿数量 * @param grid char字符型二维数组 * @return int整型 */ public int solve (char[][] grid) { // write code here //两个for循环遍历每一个格子 int count=0; for (int i = 0; i < grid.length; i++) for (int j = 0; j < grid[0].length; j++) { //只有当前格子是1才开始计算 if (grid[i][j] == '1') { //如果当前格子是1,岛屿的数量加1 count++; //然后通过bfs把当前格子的上下左右4 //个位置为1的都要置为0,因为他们是连着 //一起的算一个岛屿, bfs(grid, i, j); } } return count; } public void bfs(char[][] grid,int x,int y){ grid[x][y] = '0'; int n = grid.length; int m = grid[0].length; Queue<Integer> queue = new LinkedList<>(); int code = x * m + y; //坐标转化的值存放到队列中 queue.add(code); while (!queue.isEmpty()) { //出队 code = queue.poll(); //在反转成坐标值(i,j) int i = code / m; int j = code % m; if (i > 0 && grid[i - 1][j] == '1') {//上 //如果上边格子为1,把它置为0,然后加入到队列中 //下面同理 grid[i - 1][j] = '0'; queue.add((i - 1) * m + j); } if (i < n - 1 && grid[i + 1][j] == '1') {//下 grid[i + 1][j] = '0'; queue.add((i + 1) * m + j); } if (j > 0 && grid[i][j - 1] == '1') { //左 grid[i][j - 1] = '0'; queue.add(i * m + j - 1); } if (j < m - 1 && grid[i][j + 1] == '1') {//右 grid[i][j + 1] = '0'; queue.add(i * m + j + 1); } } } }