
[每日一题] 85. 红与黑(图、DFS)
使用广度优先搜索(BFS)遍历图形。 记录访问过的瓷砖,避免重复计算。 每当访问一个新的黑色瓷砖,增加计数器。 处理每个测试用例,确保程序循环正确。 高效处理边缘情况和大区域连通。
发布日期:2021-05-12 23:15:09
浏览次数:11
分类:精选文章
本文共 1414 字,大约阅读时间需要 4 分钟。
题目解析:
输入的m和n代表接下来会输入几行几列字符。接下来的行是瓷砖的排列,其中"."代表黑色瓷砖,"#"代表白色瓷砖,"@"表示当前所在的位置。我需要计算从这个位置出发,能够到达的所有黑色瓷砖的总数。这个问题可以通过深度优先遍历来解决,统计所有的可能性。
常见的解决方案:
代码实现:
#include#include #include #include #include using namespace std;struct pos { int x, y;};int bfs(vector > map, vector > visit, pos start) { const int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}}; queue q; int count = 1; // 包括开始的位置 q.push(start); visit[start.x][start.y] = true; while (!q.empty()) { pos current = q.front(); q.pop(); for (int i = 0; i < 4; ++i) { int newx = current.x + dirs[i][0]; int newy = current.y + dirs[i][1]; if (newx >= 0 && newx < map.size() && newy >= 0 && newy < map[0].size()) { if (!visit[newx][newy] && map[newx][newy] == '.') { visit[newx][newy] = true; count++; q.push({newx, newy}); } } } } return count;}int main() { int m, n; while (true) { cin >> m >> n; if (!m * n) break; vector > map(m, vector (n)); vector > visited(m, vector (n, false)); pos start; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { cin >> map[i][j]; if (map[i][j] == '@') { start.x = i; start.y = j; } } } int result = bfs(map, visited, start); cout << result << endl; } return 0;}
这个解决方案使用广度优先搜索来遍历所有可能的黑色瓷砖,确保每个瓷砖只被访问一次。代码结构清晰,变量命名明确,符合技术员的写作习惯。程序能够正确处理每个测试用例,输出正确结果。
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2025年04月19日 19时31分17秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
C#批量上传图片
2019-03-10
【亚马逊运营】有关滞销库存的处理方法之站外清库存法!
2019-03-10
解决TomCat中文乱码和InteliJ IDEA中文乱码问题
2019-03-10
pyhon中安装win32com模块
2019-03-10
C++错误笔记
2019-03-10
解决 MySQL 8.0 客户端连接 caching_sha2_password 问题
2019-03-10
GZIP压缩和解压缩不删除原始文件
2019-03-10
【无线通信模块】GPRS DTU不稳定和容易掉线原因
2019-03-10
CSS(六)|页面布局之定位
2019-03-10
比特币(BSV)知识库:身份-BSVAlias
2019-03-10
设计模式 - 2) 策略模式
2019-03-10
SpringBoot使用RedisTemplate简单操作Redis的五种数据类型
2019-03-10
国标流媒体服务器以ROOT身份运行提示“permission denide”报错解决
2019-03-10
如何在农业或大棚内布置互联网安防监控系统实现智慧农业?
2019-03-10