Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0613· OpenAIAi2 WildChat-4.8M (AI2)

用c++ 宽度优先遍历解:奶牛 Bessie 计划好好享受柔软的春季新草。新草分布在 R 行 C 列的牧场里。它想计算一下牧场中的草丛数量。 在牧场地图中,每个草丛要么是单个…

  1. User

    用c++ 宽度优先遍历解:奶牛 Bessie 计划好好享受柔软的春季新草。新草分布在 R 行 C 列的牧场里。它想计算一下牧场中的草丛数量。

    在牧场地图中,每个草丛要么是单个 “#”,要么是有公共边的相邻两个 “#”。给定牧场地图,计算有多少个草丛。

    例如,考虑如下 5 行 6 列的牧场地图

    .#.... ..#... ..#..# ...##. .#.... 这个牧场有 5 个草丛:一个在第一行,一个在第二列横跨了二、三行,一个在第三行,一个在第四行横跨了四、五列,最后一个在第五行。

  2. Assistant

    以下是使用宽度优先搜索算法进行解决的C++代码:

    #include <iostream>
    #include <queue>
    using namespace std;
    
    int countGrasslands(char** field, int R, int C) {
        int count = 0;
        bool** visited = new bool*[R];
        for(int i = 0; i < R; i++) {
            visited[i] = new bool[C];
            for(int j = 0; j < C; j++) {
                visited[i][j] = false;
            }
        }
    
        queue<pair<int, int>> q;
        int dx[] = {1, -1, 0, 0};
        int dy[] = {0, 0, 1, -1};
    
        for(int i = 0; i < R; i++) {
            for(int j = 0; j < C; j++) {
                if(!visited[i][j] && field[i][j] == '#') {
                    count++;
                    visited[i][j] = true;
                    q.push(make_pair(i, j));
    
                    while(!q.empty()) {
                        pair<int, int> curr = q.front();
                        q.pop();
    
                        for(int k = 0; k < 4; k++) {
                            int x = curr.first + dx[k];
                            int y = curr.second + dy[k];
    
                            if(x >= 0 && x < R && y >= 0 && y < C && !visited[x][y] && field[x][y] == '#') {
                                visited[x][y] = true;
                                q.push(make_pair(x, y));
                            }
                        }
                    }
                }
            }
        }
    
        for(int i = 0; i < R; i++) {
            delete[] visited[i];
        }
        delete[] visited;
    
        return count;
    }
    
    int main() {
        int R = 5;
        int C = 6;
        char** field = new char*[R];
        for(int i = 0; i < R; i++) {
            field[i] = new char[C];
        }
    
        field[0] = ".#....";
        field[1] = "..#...";
        field[2] = "..#..#";
        field[3] = "...##.";
        field[4] = ".#....";
    
        int numGrasslands = countGrasslands(field, R, C);
        cout << "Number of grasslands: " << numGrasslands << endl;
    
        for(int i = 0; i < R; i++) {
            delete[] field[i];
        }
        delete[] field;
    
        return 0;
    }
    

    输出:

    Number of grasslands: 5
    

    以上代码中,我们使用了一个二维布尔数组 visited 来标记每个位置是否已经被访问过。我们使用一个队列来保存当前正在访问的位置,其初始位置是一个新的草丛。然后,我们根据当前位置的上下左右位置进行遍历,将未访问过且值为 # 的位置加入队列,并将其标记为已访问。重复此过程,直到队列为空。

    最终,草丛的数量就是我们遍历算法所找到的新草丛的数量。