力扣 200.島嶼數量
給你一個由 ‘1’（陸地）和 ‘0’（水）組成的的二維網格，請你計算網格中島嶼的數量，
島嶼總是被水包圍，并且每座島嶼只能由水平方向或豎直方向上相鄰的陸地連接形成，
此外，你可以假設該網格的四條邊均被水包圍，
示例 1:
輸入:
[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
輸出:
1
示例 2:
輸入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
輸出:
3
解釋: 每座島嶼只能由水平和/或豎直方向上相鄰的陸地連接而成，
思路：
遍歷整個二維網格，遇到島嶼時將坐標插入佇列中，然后從隊首開始逐步搜索，搜索后彈出對首，遇到陸地便插入佇列，并標記其坐標，佇列為空后島嶼數量加一，
代碼：
class Solution
{
public:
int numIslands(vector<vector<char>> &grid)
{
int b = grid.size();
if (!b)
return 0;
int a = grid[0].size();
int ans = 0;
for (int i = 0; i < b; i++)
{
for (int j = 0; j < a; j++)
{
if (grid[i][j] == '1')
{
ans++;
grid[i][j] = '0';
queue<pair<int, int>> ngb;
ngb.push({i, j});
while (!ngb.empty())
{
auto x = ngb.front();
ngb.pop();
int row = x.first, col = x.second;
if (row - 1 >= 0 && grid[row - 1][col] == '1')
{
ngb.push({row - 1, col});
grid[row - 1][col] = '0';
}
if (row + 1 < b && grid[row + 1][col] == '1')
{
ngb.push({row + 1, col});
grid[row + 1][col] = '0';
}
if (col - 1 >= 0 && grid[row][col - 1] == '1')
{
ngb.push({row, col - 1});
grid[row][col - 1] = '0';
}
if (col + 1 < a && grid[row][col + 1] == '1')
{
ngb.push({row, col + 1});
grid[row][col + 1] = '0';
}
}
}
}
}
return ans;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/44667.html
標籤：其他
上一篇：C. Link Cut Centroids(求樹的重心)
下一篇：K8s概述：幾種集群方案的對比