LeetCode Daily Question 18

Apr 7th 2022

4 月 7 日 每日一题

题目：Number of Islands:

In this problem, you will be implementing the number of islands() function, as shown below:
int number_of_islands(std::vector<std::vector> &grid);
This function takes in a 2-D grid map filled with land (represented using the character ’o’) and water (represented using the character ’.’) and returns the number of islands that exist in the map. An island is formed by connecting adjacent land characters either horizontally or vertically. In other words, if two land characters are adjacent to each other horizontally or vertically, then they are a part of the same island.

思路

今天这道题并不是 leetcode，做法和昨天的 547 类似，在主函数遍历地图所有点，遇到新的地图时调用 BFS。本道题 BFS 使用了 queue 的写法。

代码

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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
struct dequePoint
{
    uint32_t x = 0;
    uint32_t y = 0;
};

bool valid(std::vector<std::vector<char>>& grid, uint32_t x, uint32_t y){
    if(x >= 0 && x < grid[0].size() && y >= 0 && y < grid.size())
        return grid[y][x] == 'o' ? true : false;
    return false;
}

void bfsHelper(std::vector<std::vector<char>>& grid, uint32_t x, uint32_t y){
    queue<dequePoint> queue;
    queue.push(dequePoint{x,y});
    grid[y][x] = 'x';
    while(!queue.empty()){
        x = queue.front().x;
        y = queue.front().y;
        queue.pop();
        if(valid(grid, x - 1, y)){
            queue.push(dequePoint{x - 1,y});
            grid[y][x - 1] = 'x';
        }
        if(valid(grid, x + 1, y)){
            queue.push(dequePoint{x + 1,y});
            grid[y][x + 1] = 'x';
        }
        if(valid(grid, x, y - 1)){
            queue.push(dequePoint{x,y - 1});
            grid[y - 1][x] = 'x';
        }
        if(valid(grid, x, y + 1)){
            queue.push(dequePoint{x,y + 1});
            grid[y + 1][x] = 'x';
        }
    }
}

int number_of_islands(std::vector<std::vector<char>>& grid) {
    uint32_t islandNum = 0;
    for(uint32_t i = 0; i < grid.size(); i++){
        for(uint32_t j = 0; j < grid[0].size(); j++){
            if(grid[i][j] == 'o'){
                islandNum++;
                bfsHelper(grid, j, i);
            }
        }
    }
    return static_cast<int>(islandNum);
}

,
  1. 4 月 7 日 每日一题
    1. 题目：Number of Islands:
    2. 思路
    3. 代码