yxy

用户名：dotcpp0787179

访问量：491

签　名：

竞赛交流论坛： blog.qzcy2.top 欢迎来撩！

等　　级
排　　名	976
经　　验	3389
参赛次数	3
文章发表	23
年　　龄	1
在职情况	学生
学　　校	内江师范学院
专　　业	纳西妲系

　　自我简介：

我不会

TA的其他文章

[食物链] 并查集 - NOI2001 提高组
浏览：22

[金银岛]自定义排序优先'均权'最大--我看题解都太复杂辣
浏览：53

杀到这九天十地无人敢称尊,直到身边再无一人能陪我征战,叶天帝不过如此
浏览：34

你可能喜欢

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）scanf后面加个getchar（），收掉回车符，就可以用gets了

bfs-Blood Fill 算法—[The Castle]

　　作者: yxy　　　　发表时间：2024-09-17 15:47:01 浏览：23　|　评论：1　

原题链接：信息学奥赛一本通T1250-The Castle

# Blood Fill 算法
###### 这是一个 寻找连通块很好用的一个方法
原理 ： 类似于洪水填充 将指定的同类连通块全部填充成一种类型 或 找到一个需要的元素 从此位置向四周联通的 具有相同属性的扩散 也就是bfs原理了

###### 本题只需要 计算墙的位置就好 其他的就很简单了 
###### 通过题面 四个方向的墙体会用 二进制数来表示 所以我们需要用到位运算
简单的计算一下 西墙1 ：0001 北墙2 ：0010 东墙4 ： 0100 南墙 ： 1000；
###### 通过 按位与 & 来判断 是否有墙体；；

###### Code：
```cpp
    #include <iostream>
    #include <algorithm>
    #include <cstring>
    #include <queue>
    #define int long long	//个人习惯 有备无患

using namespace std;

const int N = 55;
    typedef pair <int , int> PII;
    queue<PII> q;
    int n , m;
    int g[N][N];
    bool ch[N][N];
    int ans , area;

int dx[] = {0 , -1 , 0 , 1} , dy[] = {-1 , 0 , 1 , 0};	//按照墙体从小到大历遍

int bfs(int x , int y)
    {
        q.push({x , y});
        ch[x][y] = true;  //入点标记为已走过
        int res = 0;		//初始化面积

while (!q.empty())
        {
            PII t = q.front();
            q.pop();
            res ++;
            
            for (int i = 0 ; i < 4 ; i ++ ) 
            {
                int xx = t.first + dx[i] , yy = t.second + dy[i];
                if (xx < 1 || xx >= n + 1 || yy < 1 || yy >= m + 1) continue;
                if (ch[xx][yy]) continue;
                if (g[t.first][t.second] >> i & 1) continue; //判断是否有墙体

q.push({xx , yy});
                ch[xx][yy] = true;
            }
        }

return res;
    }
    signed main()
    {
        cin >> n >> m;
        for (int i = 1 ; i <= n ; i ++ )
            for (int j = 1 ; j <= m ; j ++ )
                cin >> g[i][j];
        
        for (int i = 1 ; i <= n ; i ++ )
        {
            for (int j = 1 ; j <= m ; j ++ )
            {
                if (!ch[i][j]) //挨个找 找过的做标记
                {
                    area = max(area , bfs(i , j));	//返回最大房间面积并更新area
                    ans ++; //房间数量
                }
            }
        }
        
        cout << ans << endl;
        cout << area << endl;

return 0;
    }
```

0.0分

1 人评分

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

　　评论区

109徐守佳

2024-09-18 09:46:57

yxy

TA的其他文章

你可能喜欢

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

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

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

化学品问题（C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）scanf后面加个getchar（），收掉回车符，就可以用gets了

bfs-Blood Fill 算法—[The Castle]

评论区

精彩推荐

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

程序员的表白（C语言代码）

printf基础练习2 （C语言代码）

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

蚂蚁感冒（C语言代码）

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

单词个数统计（C语言代码）

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

小O的图案（C语言代码）

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

yxy

TA的其他文章

你可能喜欢

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

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

2005年春浙江省计算机等级考试二级C 编程题(1) （C语言代码）

化学品问题 （C语言代码）

C语言程序设计教程（第三版）课后习题10.7 （C语言代码）scanf后面加个getchar（），收掉回车符，就可以用gets了

bfs-Blood Fill 算法—[The Castle]

评论区

精彩推荐

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

程序员的表白 （C语言代码）

printf基础练习2 （C语言代码）

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

蚂蚁感冒 （C语言代码）

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

单词个数统计 （C语言代码）

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

小O的图案 （C语言代码）

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

化学品问题（C语言代码）

　　评论区

程序员的表白（C语言代码）

蚂蚁感冒（C语言代码）

单词个数统计（C语言代码）

小O的图案（C语言代码）