LeetCode 200.岛屿数量
本帖最后由 798236606 于 2020-3-4 17:23 编辑传送门：https://leetcode-cn.com/problems/number-of-islands/
解：
1.深度优先遍历(C)
void DFS(int x, int y, char** grid, int nr, int nc)
{
++grid;
if (x - 1 >= 0 && grid == '1') DFS(x - 1, y, grid, nr, nc);
if (x + 1 < nr && grid == '1') DFS(x + 1, y, grid, nr, nc);
if (y - 1 >= 0 && grid == '1') DFS(x, y - 1, grid, nr, nc);
if (y + 1 < nc && grid == '1') DFS(x, y + 1, grid, nr, nc);
}
int numIslands(char** grid, int gridSize, int* gridColSize)
{
if (!grid || !gridSize || !*gridColSize) return 0;
int num = 0;
for (int i = 0; i < gridSize; ++i)
for (int j = 0; j < *gridColSize; ++j)
if (grid == '1' && ++num)
DFS(i, j, grid, gridSize, *gridColSize);
return num;
}
2.广度优先遍历(C++)
class Solution {
public:
void BFS(int x, int y, vector< vector<char> > &grid, int nr, int nc)
{
queue< pair<int, int> > q;
q.push({x, y});
while (!q.empty())
{
x = q.front().first, y = q.front().second;
q.pop();
if (x - 1 >= 0 && grid == '1' && ++grid) q.push({x - 1, y});
if (x + 1 < nr && grid == '1' && ++grid) q.push({x + 1, y});
if (y - 1 >= 0 && grid == '1' && ++grid) q.push({x, y - 1});
if (y + 1 < nc && grid == '1' && ++grid) q.push({x, y + 1});
}
}
int numIslands(vector< vector<char> > &grid)
{
if (!grid.size()) return 0;
int nr = grid.size(), nc = grid.size(), num = 0;
for (int i = 0; i < nr; ++i)
for (int j = 0; j < nc; ++j)
if (grid == '1' && ++num)
BFS(i, j, grid, nr, nc);
return num;
}
};
页:
[1]