DFS专题：力扣岛屿问题
一、岛屿数量
题目链接: 200.岛屿数量
题目描述
代码思路
使用for对每一个网格点进行判断，如果遇到未搜索过的’1’，则使岛屿数加一，并利用dfs将与其相连的‘1’都进行标记，确保每次搜索到1都是一个新的岛屿。
代码纯享版
class Solution {
public int numIslands(char[][] grid) {
int len = grid.length;
int wide = grid[0].length;
int sum = 0;
for(int i = 0; i < len; i++){
for(int j = 0; j < wide; j++){
if(grid[i][j] == '1'){
sum++;
dfs(grid, i, j);
}
}
}
return sum;
}
void dfs(char[][] grid, int i, int j){
int len = grid.length;
int wide = grid[0].length;
if(i < 0 || i >= len || j < 0 || j >= wide || grid[i][j] != '1'){
return;
}
grid[i][j] = '2';
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
}
代码逐行解析版
class Solution {
public int numIslands(char[][] grid) {
int len = grid.length; //岛屿长度
int wide = grid[0].length; //岛屿宽度
int sum = 0; //岛屿总数
//遍历岛屿每一个位置
for(int i = 0; i < len; i++){
for(int j = 0; j < wide; j++){
if(grid[i][j] == '1'){ //如果为陆地
sum++; //岛屿总数加一
dfs(grid, i, j); //dfs
}
}
}
return sum;
}
//深度搜索所有连接在一起的'1',将其变为'2'
//grid[i][j] == '0' 水
//grid[i][j] == '1' 未搜索的陆地
//grid[i][j] == '2' 已搜索的陆地
void dfs(char[][] grid, int i, int j){
int len = grid.length;
int wide = grid[0].length;
//排除2种情况
//1.超出网格范围的搜索
//2.不是未搜索的陆地
if(i < 0 || i >= len || j < 0 || j >= wide || grid[i][j] != '1'){
return;
}
grid[i][j] = '2'; //将grid[i][j] == '1'的情况标记为'2'
//上下左右四个方位的搜索
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j - 1);
dfs(grid, i, j + 1);
}
}
二、岛屿的周长
题目链接: 463.岛屿的周长
题目描述
代码思路
利用for循环遍历到一块陆地后，对这块陆地进行dfs搜索，遇到海洋或超出区域的部分，则周长加一；遇到未搜索过的陆地，则标记为搜索过；遇到搜索过的陆地，直接返回。
代码纯享版
class Solution {
public int area = 0;
public int islandPerimeter(int[][] grid) {
int len = grid.length;
int wide = grid[0].length;
int i = 0, j = 0;
int judge = 1;
for(i = 0; i < len; i++){
for(j = 0; j < wide; j++){
if(grid[i][j] == 1){
dfs(grid, i , j);
return area;
}
}
}
return 0;
}
void dfs(int[][] grid, int i, int j){
int len = grid.length;
int wide = grid[0].length;
if(i < 0 || i >= len || j < 0 || j >= wide || grid[i][j] == 0){
area++;
return;
}
if(grid[i][j] == 2){
return;
}
grid[i][j] = 2;
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
}
代码逐行解析版
class Solution {
public int area = 0; //设周长为公共变量
public int islandPerimeter(int[][] grid) {
int len = grid.length;
int wide = grid[0].length;
for(int i = 0; i < len; i++){
for(int j = 0; j < wide; j++){
if(grid[i][j] == 1){ //碰到陆地，进行dfs
dfs(grid, i , j);
return area; //只有一块岛屿，所以搜索一次后即可返回周长
}
}
}
return 0; //没找到岛屿，返回0
}
void dfs(int[][] grid, int i, int j){
int len = grid.length;
int wide = grid[0].length;
//由题目图可知，搜索到超出区域范围或海洋位置的，周长加一
if(i < 0 || i >= len || j < 0 || j >= wide || grid[i][j] == 0){
area++;
return;
}
if(grid[i][j] == 2){ //已搜索过的直接返回
return;
}
grid[i][j] = 2; //把未搜索过的陆地标记为2:已搜索过的陆地
//对上下左右进行搜索
dfs(grid, i - 1, j);
dfs(grid, i + 1, j);
dfs(grid, i, j + 1);
dfs(grid, i, j - 1);
}
}
