題目
鏈接(https://leetcode-cn.com/problems/number-of-islands/)
給定一個(gè)由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格樟澜，計(jì)算島嶼的數(shù)量梅肤。一個(gè)島被水包圍，并且它是通過(guò)水平方向或垂直方向上相鄰的陸地連接而成的掩缓。你可以假設(shè)網(wǎng)格的四個(gè)邊均被水包圍谆甜。
示例 1:
輸入:
11110
11010
11000
00000
輸出: 1
示例 2:
輸入:
11000
11000
00100
00011
輸出: 3
分析
這道題目相對(duì)簡(jiǎn)單
首先遍歷這個(gè)二維數(shù)組蓄诽，遇到1 功偿，就計(jì)數(shù)加一筑舅，然后把這個(gè)坐標(biāo)添加到stack里面座慰。
取stack頂部陨舱，遍歷翠拣。遍歷的方法是上下左右一直遍歷。
如上遍歷：i--,遇到1就把1改成0游盲，然后添加到tack中只到遇到0或者超出邊界
代碼
class Solution {
public int numIslands(char[][] grid) {
//島嶼計(jì)數(shù)
int account = 0;
//還未遍歷的點(diǎn)
Stack<int[]> stack = new Stack<>();
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j]=='1'){
//遇到島嶼 計(jì)數(shù)加一
account++;
int [] temp = {i,j};
//然后入棧
stack.push(temp);
while (!stack.empty()){
//取出未遍歷的點(diǎn)
int[] top = stack.pop();
//遍歷上下左右四個(gè)方向
turnRight(grid,top[0],top[1],stack);
turnLeft(grid,top[0],top[1],stack);
turnUp(grid,top[0],top[1],stack);
turnDown(grid,top[0],top[1],stack);
}
}
}
}
return account;
}
//left遍歷误墓，一直向lefg遍歷，直到遇到0或者超出邊界益缎。遇到1則把1變成0谜慌，然后把這個(gè)點(diǎn)放入為遍歷的stack
private void turnLeft(char[][] grid, int i, int j, Stack<int[]> stack) {
while ((j+1<grid[i].length) && grid[i][j+1]=='1'){
j++;
grid[i][j]='0';
int[] temp = {i,j};
stack.push(temp);
}
}
private void turnRight(char[][] grid, int i, int j, Stack<int[]> stack) {
while ((j-1>=0) && grid[i][j-1]=='1'){
j--;
grid[i][j]='0';
int[] temp = {i,j};
stack.push(temp);
}
}
private void turnUp(char[][] grid, int i, int j, Stack<int[]> stack) {
while ((i-1>=0) && grid[i-1][j]=='1'){
i--;
grid[i][j]='0';
int[] temp = {i,j};
stack.push(temp);
}
}
private void turnDown(char[][] grid, int i, int j, Stack<int[]> stack) {
while ((i+1<grid.length) && grid[i+1][j]=='1'){
i++;
grid[i][j]='0';
int[] temp = {i,j};
stack.push(temp);
}
}
}
結(jié)果
image.png
