在做島嶼類問題的時候請先看作者：nettee的題解右遭，講的真的特別好懈叹，看了他的題解在自己做題９愿堋！３纬伞ｋ嗜鳌畏吓！
鏈接：https://leetcode.cn/problems/number-of-islands/solution/dao-yu-lei-wen-ti-de-tong-yong-jie-fa-dfs-bian-li-/
200. 島嶼數(shù)量
image.png
這道題的思路是用dfs遍歷連續(xù)1的點倒彰，同時遍歷的時候記得要把遍歷過的1變成2昆婿，這樣子后面才不會重復(fù)遍歷或者進(jìn)入繞圈圈的情況。
圖的遍歷模板就是這個：
void dfs(int[][] grid, int r, int c) {
// 判斷 base case
if (!inArea(grid, r, c)) {
return;
}
// 如果這個格子不是島嶼婿斥，直接返回
if (grid[r][c] != 1) {
return;
}
grid[r][c] = 2; // 將格子標(biāo)記為「已遍歷過」
// 訪問上汛兜、下巴粪、左、右四個相鄰結(jié)點
dfs(grid, r - 1, c);
dfs(grid, r + 1, c);
dfs(grid, r, c - 1);
dfs(grid, r, c + 1);
}
// 判斷坐標(biāo) (r, c) 是否在網(wǎng)格中
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
所以完整ac答案如下：
class Solution {
public int numIslands(char[][] grid) {
int row = grid.length;
int col = grid[0].length;
int count = 0;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(grid[i][j]=='1'){
dfs(grid,i,j);
count++;
}
}
}
return count;
}
public void dfs(char[][] grid,int i,int j){
if(!isArea(grid,i,j)){
return ;
}
if(grid[i][j]!='1'){
return;
}
grid[i][j] = '2';
dfs(grid,i-1,j);
dfs(grid,i,j-1);
dfs(grid,i+1,j);
dfs(grid,i,j+1);
}
public boolean isArea(char[][] grid,int i,int j){
return i>=0&&i<grid.length&&j>=0&&j<grid[0].length;
}
}
695. 島嶼的最大面積
image.png
解題思路和上面的差不多粥谬，就是在dfs的時候記錄一下到底有多少個1肛根，然后保留最大值就行
static int ans =0 ;
static int res = 0;
public int maxAreaOfIsland(int[][] grid) {
int row = grid.length;
int col = grid[0].length;
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
if(grid[i][j]==1){
dfs(grid,i,j);
ans = Math.max(ans,res);
res = 0;
}
}
}
return ans;
}
public void dfs(int[][] grid,int i,int j){
if(!isArea(grid,i,j)){
return ;
}
if(grid[i][j]!=1){
return;
}
grid[i][j] = 2;
res++;
dfs(grid,i-1,j);
dfs(grid,i,j-1);
dfs(grid,i+1,j);
dfs(grid,i,j+1);
}
public boolean isArea(int[][] grid,int i,int j){
return i>=0&&i<grid.length&&j>=0&&j<grid[0].length;
}
463. 島嶼的周長
image.png
這道題用數(shù)學(xué)的方式做其實比用dfs來的好理解和塊，但是既然是訓(xùn)練模板漏策，所以還是嘗試用dfs解決派哲，這邊動用了一個很巧妙的思想，就是dfs邊界的問題掺喻，第一種情況是dfs到了一個1芭届，他的其他方向沒有1了，這時候返回感耙，相當(dāng)于多了一個海洋的邊界褂乍；另一個情況是dfs遍歷到了矩陣的四周，返回的話就一個邊界的邊即硼。
class Solution {
public int islandPerimeter(int[][] grid) {
for (int r = 0; r < grid.length; r++) {
for (int c = 0; c < grid[0].length; c++) {
if (grid[r][c] == 1) {
// 題目限制只有一個島嶼逃片，計算一個即可
return dfs(grid, r, c);
}
}
}
return 0;
}
int dfs(int[][] grid, int r, int c) {
// 函數(shù)因為「坐標(biāo) (r, c) 超出網(wǎng)格范圍」返回，對應(yīng)一條黃色的邊
if (!inArea(grid, r, c)) {
return 1;
}
// 函數(shù)因為「當(dāng)前格子是海洋格子」返回只酥，對應(yīng)一條藍(lán)色的邊
if (grid[r][c] == 0) {
return 1;
}
// 函數(shù)因為「當(dāng)前格子是已遍歷的陸地格子」返回褥实，和周長沒關(guān)系
if (grid[r][c] != 1) {
return 0;
}
grid[r][c] = 2;
return dfs(grid, r - 1, c)
+ dfs(grid, r + 1, c)
+ dfs(grid, r, c - 1)
+ dfs(grid, r, c + 1);
}
// 判斷坐標(biāo) (r, c) 是否在網(wǎng)格中
boolean inArea(int[][] grid, int r, int c) {
return 0 <= r && r < grid.length
&& 0 <= c && c < grid[0].length;
}
}
