星空追忆

用户名：StarrySky2020

访问量：857

签　名：

等　　级
排　　名	11970
经　　验	998
参赛次数	0
文章发表	7
年　　龄	19
在职情况	学生
学　　校	南京林业大学
专　　业	软件工程

　　自我简介：

TA的其他文章

全球变暖BFS
浏览：118

你可能喜欢

全球变暖BFS

　　作者: 星空追忆　　　　发表时间：2022-04-08 11:55:20 浏览：118　|　评论：0　

原题链接：蓝桥杯2018年第九届真题-全球变暖

宽搜解法
	#include <iostream>
    #include <queue>
    #include <cstring>
    using namespace std;
    
    const int N = 1010;
    
    int n;
    string  g[N];
    bool vis[N][N];
    int cnt;
    int dx[4] = {1, 0, -1, 0};
    int dy[4] = {0, -1, 0, 1};
    
    void bfs(int x, int y, int &total, int &bound)
    {
        queue<pair<int, int> > q;
        q.push({x, y});
        vis[x][y] = true;
        
        while(!q.empty())
        {
            auto t = q.front();
            q.pop();
            total++;
            bool is_bound = false;
            
			//遍历四个方向上的点
            for(int i = 0; i < 4; i++)
            {
                int tx = t.first + dx[i];
                int ty = t.second + dy[i];
                if(tx < 0 || ty < 0 || tx >= n || ty >= n)  //越界
                    continue;
                if(vis[tx][ty]) //已经访问过
                    continue;
                if(g[tx][ty] == '.') //边界岛屿 及时continue， 因为一个边界岛屿旁边可能会有多个'.'所以用 is——bound标识
                {
                    is_bound = true;
                    continue;
                }
                q.push({tx, ty});
                vis[tx][ty] = true;
            }
            if(is_bound) bound++;
        }
    }
    int main(void)
    {
        cin >> n;
        
        for(int i = 0; i < n; i++)
            cin >> g[i];
        
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(!vis[i][j] && g[i][j] == '#')
                {
				//bound为边界点 将要淹没的岛屿
				//total为这个连通块的所有岛屿
                    int total = 0, bound = 0;
                    bfs(i, j, total, bound);
					//当边界岛屿个数与整个岛屿个数相同时，说明这个大岛将全部被淹没
                    if(bound == total)  cnt++;
                }
                
            }
        }
        
        cout << cnt << endl;
        
        return 0;
    }

0.0分

1 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

精彩推荐

小九九（C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

不容易系列（C语言代码）

不会做的

输出正反三角形（C语言代码）格式错误！！！

A+B for Input-Output Practice (V) （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

矩阵乘方（C语言代码）

C二级辅导-分段函数（C语言代码）

C二级辅导-等差数列（C语言代码）

星空追忆

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

单词个数统计（C++代码）

勾股数（Java代码）

C语言程序设计教程（第三版）课后习题6.2 （C++代码）

点我有惊喜！你懂得！

全球变暖BFS

评论区

精彩推荐

小九九（C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

不容易系列（C语言代码）

不会做的

输出正反三角形（C语言代码）格式错误！！！

A+B for Input-Output Practice (V) （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

矩阵乘方（C语言代码）

C二级辅导-分段函数（C语言代码）

C二级辅导-等差数列（C语言代码）

星空追忆

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题5.4 （C语言代码）

单词个数统计 （C++代码）

勾股数 （Java代码）

C语言程序设计教程（第三版）课后习题6.2 （C++代码）

点我有惊喜！你懂得！

全球变暖BFS

评论区

精彩推荐

小九九 （C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数 （C语言代码）

不容易系列 （C语言代码）

不会做的

输出正反三角形 （C语言代码）格式错误！！！

A+B for Input-Output Practice (V) （C语言代码）

C语言程序设计教程（第三版）课后习题8.6 （C语言代码）

矩阵乘方 （C语言代码）

C二级辅导-分段函数 （C语言代码）

C二级辅导-等差数列 （C语言代码）

单词个数统计（C++代码）

勾股数（Java代码）

　　评论区

小九九（C语言代码）

C语言训练-求具有abcd=(ab+cd)2性质的四位数（C语言代码）

不容易系列（C语言代码）

输出正反三角形（C语言代码）格式错误！！！

矩阵乘方（C语言代码）

C二级辅导-分段函数（C语言代码）

C二级辅导-等差数列（C语言代码）