200. Количество островов (Number of Islands)
Задание.
Получена двумерная (2D) двоичная сетка grid, размером m x n , которая представляет карту ‘1’ (суша) и ‘0’ (вода).
Верните количество островов.
Остров окружен водой и образуется путем соединения соседних земель по горизонтали или вертикали. Предполагается, что все четыре края сетки окружены водой.
Пример 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
Решение.
class Solution {
private:
void visit(int row, int col, vector<vector<int>> &vis, queue<pair<int,int>> &q, vector<vector<char>> &grid)
{
int n=grid.size();
int m=grid[0].size();
if(row>=0 && row<n && col>=0 && col<m && !vis[row][col] && grid[row][col]=='1' ) {
vis[row][col]=1;
q.push({row,col});
}
}
void bfs(int row, int col, vector<vector<int>> &vis, vector<vector<char>> &grid)
{
vis[row][col] = 1;
queue<pair<int,int>> q;
q.push({row, col});
while(!q.empty()) {
int nrow = q.front().first;
int ncol = q.front().second;
q.pop();
visit(nrow, ncol, vis, q, grid);
visit(nrow-1, ncol, vis, q, grid);
visit(nrow+1, ncol, vis, q, grid);
visit(nrow, ncol-1, vis, q, grid);
visit(nrow, ncol+1, vis, q, grid);
}
}
public:
int numIslands(vector<vector<char>>& grid)
{
int n=grid.size();
int m=grid[0].size();
vector<vector<int>> vis(n,vector<int>(m,0));
int cnt = 0;
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
if(!vis[i][j] && grid[i][j]=='1' ) {
cnt++;
bfs(i,j,vis, grid);
}
}
}
return cnt;
}
};
Способ решения.
Используется техника обхода графа вширь (BFS). Подробнее описано здесь.
Существуют следующие техники обхода деревьев:
-
прямой (root – left – right)
-
симметричный (left – root – right)
-
обратный (left – right – root)