[每日一题] 85. 红与黑(图、DFS)
发布日期:2021-05-12 23:15:09 浏览次数:11 分类:精选文章

本文共 1414 字,大约阅读时间需要 4 分钟。

题目解析:

输入的m和n代表接下来会输入几行几列字符。接下来的行是瓷砖的排列,其中"."代表黑色瓷砖,"#"代表白色瓷砖,"@"表示当前所在的位置。我需要计算从这个位置出发,能够到达的所有黑色瓷砖的总数。这个问题可以通过深度优先遍历来解决,统计所有的可能性。

常见的解决方案:

  • 使用广度优先搜索(BFS)遍历图形。
  • 记录访问过的瓷砖,避免重复计算。
  • 每当访问一个新的黑色瓷砖,增加计数器。
  • 处理每个测试用例,确保程序循环正确。
  • 高效处理边缘情况和大区域连通。
  • 代码实现:

    #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;}

    这个解决方案使用广度优先搜索来遍历所有可能的黑色瓷砖,确保每个瓷砖只被访问一次。代码结构清晰,变量命名明确,符合技术员的写作习惯。程序能够正确处理每个测试用例,输出正确结果。

    上一篇:[每日一题] 86. 蘑菇阵(动态规划、概率计算、边界问题)
    下一篇:[每日一题] 84. mkdir(字符串、逻辑)

    发表评论

    最新留言

    路过,博主的博客真漂亮。。
    [***.116.15.85]2025年04月19日 19时31分17秒

    关于作者

        喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
    -- 愿君每日到此一游!

    推荐文章

    C#批量上传图片 2019-03-10
    【亚马逊运营】有关滞销库存的处理方法之站外清库存法! 2019-03-10
    PyCharm使用笔记之同一目录下文件调用出现红线Unresolved Reference... 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
    比特币(BSV)知识库:网络-比特币测试用区块链(Bitcoin Test Blockchains) 2019-03-10
    设计模式 - 2) 策略模式 2019-03-10
    SpringBoot使用RedisTemplate简单操作Redis的五种数据类型 2019-03-10
    国标流媒体服务器以ROOT身份运行提示“permission denide”报错解决 2019-03-10
    国标流媒体服务器在linux系统运行提示fork/exec ……/redis/redis-server错误解决方案 2019-03-10
    国标GB28181协议视频推流平台EasyGBD在Linux下编译报“UINT64_C在此作用领域中尚未声明”错误 2019-03-10
    视频流媒体服务器RTSP拉流、RTMP推流流媒体服务器授权方案之加密机运行后无法授权问题解决 2019-03-10
    安防摄像机网页无插件直播方案EasyNVR关于接口调用出现401 Unauthorized问题的解决方法 2019-03-10
    如何在农业或大棚内布置互联网安防监控系统实现智慧农业? 2019-03-10