QeuroIzoのBlog

hello world

0%

32. 岛屿的个数

发表于

题目

解析

同 733. 图像渲染

代码

  • DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
void dfs(vector<vector<char>>& grid, int x, int y)
{
    int next[4][2] = { {0, 1}, {1, 0},  {0, -1}, {-1, 0} };
    grid[x][y] = '0';
    for(int i = 0; i < 4; i++) {
        int nx = x + next[i][0];
        int ny = y + next[i][1];
        if(nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && grid[nx][ny] == '1')
            dfs(grid, nx, ny);
    }

}

int numIslands(vector<vector<char>>& grid) {
    if(grid.empty() || grid[0].empty())
        return 0;
    int res = 0;
    int m = grid.size(), n = grid[0].size();
    for(int i = 0; i < m; i++) 
        for(int j = 0; j < n; j++) 
            if(grid[i][j] == '1') {
                res++;
                dfs(grid, i, j);
            }

    return res;
}

  • BFS

    RE?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int numIslands(vector<vector<char>>& grid) {
    if(grid.empty() || grid[0].empty())
        return 0;
    int next[4][2] = { {0, 1}, {1, 0}, {0, -1}, {-1, 0} };
    int landCount = 0;
    for(int i = 0; i < grid.size(); i++) {
        for(int j = 0; j < grid[0].size(); j++) {

            if(grid[i][j] == '1') {
                landCount++;
                queue<pair<int, int> > q;
                q.push(pair<int, int> (i, j));
                while(q.size()) {
                    pair<int, int> t = q.front();
                    q.pop();
                    grid[t.first][t.second] = '0';
                    for(int k = 0; k < 4; k++) {
                        int ni = t.first + next[k][0], nj = t.second + next[k][1];
                        if(ni >= 0 && ni < grid.size() && nj >= 0 && nj < grid[0].size() && grid[ni][nj] == '1')
                            q.push(pair<int, int> (ni, nj));
                    }
                }
            }
        }
    }
    return landCount;
}