LeetCode 200.岛屿数量

798236606

传送门：https://leetcode-cn.com/problems/number-of-islands/

解：
1.深度优先遍历(C)

void DFS(int x, int y, char** grid, int nr, int nc)
{
    ++grid[x][y];

    if (x - 1 >= 0 && grid[x - 1][y] == '1') DFS(x - 1, y, grid, nr, nc);
    if (x + 1 < nr && grid[x + 1][y] == '1') DFS(x + 1, y, grid, nr, nc);
    if (y - 1 >= 0 && grid[x][y - 1] == '1') DFS(x, y - 1, grid, nr, nc);
    if (y + 1 < nc && grid[x][y + 1] == '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[i][j] == '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[x - 1][y] == '1' && ++grid[x - 1][y]) q.push({x - 1, y});
            if (x + 1 < nr && grid[x + 1][y] == '1' && ++grid[x + 1][y]) q.push({x + 1, y});
            if (y - 1 >= 0 && grid[x][y - 1] == '1' && ++grid[x][y - 1]) q.push({x, y - 1});
            if (y + 1 < nc && grid[x][y + 1] == '1' && ++grid[x][y + 1]) q.push({x, y + 1});
        }
    }
    
    int numIslands(vector< vector<char> > &grid) 
    {
        if (!grid.size()) return 0;
        
        int nr = grid.size(), nc = grid[0].size(), num = 0;
        for (int i = 0; i < nr; ++i)
            for (int j = 0; j < nc; ++j)
                if (grid[i][j] == '1' && ++num)
                    BFS(i, j, grid, nr, nc);
        
        return num;
    }
};