一堡赔、題目
給你一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格瞳腌，請(qǐng)你計(jì)算網(wǎng)格中島嶼的數(shù)量。
島嶼總是被水包圍袋励，并且每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成柒昏。
此外凳宙，你可以假設(shè)該網(wǎng)格的四條邊均被水包圍。
二职祷、示例
示例 1：
【輸入】grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
【輸出】1
示例 2：
【輸入】grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
【輸出】3
提示：
- m == grid.length
- n == grid[i].length
-
1<= m, n <=300 - grid[i][j] 的值為 '
0' 或 '1'
三氏涩、解題思路
根據(jù)題目描述，每座島嶼只能由水平方向和/或豎直方向上相鄰的陸地連接形成有梆。那么我們就可以通過(guò)對(duì)某個(gè)格子的上方向是尖、下方向、左方向和右方向進(jìn)行遍歷泥耀，來(lái)判斷每個(gè)島嶼了饺汹。
在遍歷過(guò)程中，由于我們是針對(duì)每一個(gè)格子都進(jìn)行上下左右四個(gè)方向的遍歷痰催，所以兜辞，會(huì)出現(xiàn)重復(fù)遍歷相同格子的情況發(fā)生，那么我們就需要進(jìn)行如下的判斷邏輯防止這種情況發(fā)生了：
【判斷1】遍歷的格子不能越界陨囊；
【判斷2】遍歷到的格子如果是1弦疮，才繼續(xù)遍歷夹攒，否則終止該方向的遍歷蜘醋；
【判斷3】只要遍歷到的格子是1，則將該格子值變?yōu)?code>0（防止重復(fù)遍歷值為1的格子）咏尝；
以上就是判斷一個(gè)島嶼的方式压语，當(dāng)我們將整個(gè)數(shù)組都遍歷完畢后啸罢，就可以統(tǒng)計(jì)出來(lái)一共有多少的島嶼數(shù)目了。為了便于大家理解胎食，下面我們以輸入grid = [["1","1","0","0","0"],["1","1","0","0","0"], ["0","0","1","0","0"],["0","0","0","1","1"]]為例扰才，看一下具體的操作流程是怎么樣的。請(qǐng)見(jiàn)下圖所示：
四厕怜、代碼實(shí)現(xiàn)
class Solution {
int result = 0;
char[][] grid;
public int numIslands(char[][] grid) {
this.grid = grid;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
dfs(i, j);
result++;
}
}
}
return result;
}
public void dfs(int i, int j) {
if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') return;
grid[i][j] = '0';
dfs(i - 1, j); // 向上遍歷
dfs(i + 1, j); // 向下遍歷
dfs(i, j - 1); // 向左遍歷
dfs(i, j + 1); // 向右遍歷
}
}
今天的文章內(nèi)容就這些了：
寫(xiě)作不易衩匣，筆者幾個(gè)小時(shí)甚至數(shù)天完成的一篇文章，只愿換來(lái)您幾秒鐘的 點(diǎn)贊 & 分享 粥航。
更多技術(shù)干貨琅捏，歡迎大家關(guān)注公眾號(hào)“爪哇繆斯” ~ \(o)/ ~ 「干貨分享，每天更新」
