【蓝桥杯】信号覆盖范围——BFS(java题解)

这篇具有很好参考价值的文章主要介绍了【蓝桥杯】信号覆盖范围——BFS(java题解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

问题描述


  小蓝负责一块区域的信号塔安装,整块区域是一个长方形区域,建立坐标轴后,西南角坐标为 (0, 0), 东南角坐标为 (W, 0), 西北角坐标为 (0, H), 东北角坐标为 (W, H)。其中 W, H 都是整数。
  他在 n 个位置设置了信号塔,每个信号塔可以覆盖以自己为圆心,半径为 R 的圆形(包括边缘)。
  为了对信号覆盖的情况进行检查,小蓝打算在区域内的所有横纵坐标为整数的点进行测试,检查信号状态。其中横坐标范围为 0 到 W,纵坐标范围为 0 到 H,总共测试 (W+1) * (H+1) 个点。
  给定信号塔的位置,请问这 (W+1)*(H+1) 个点中有多少个点被信号覆盖。
输入格式
  输入第一行包含四个整数 W, H, n, R,相邻整数之间使用一个空格分隔。
  接下来 n 行,每行包含两个整数 x, y,表示一个信号塔的坐标。信号塔可能重合,表示两个信号发射器装在了同一个位置。
输出格式
  输出一行包含一个整数,表示答案。
样例输入
10 10 2 5
0 0
7 0
样例输出
57
评测用例规模与约定
  对于所有评测用例,1 <= W, H <= 100,1 <= n <= 100, 1 <= R <= 100, 0 <= x <= W, 0 <= y <= H。文章来源地址https://www.toymoban.com/news/detail-406671.html

题目代码 

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class 信号覆盖范围 {
    static int w, h, n, r, count = 0;
    static boolean st[][] = new boolean[110][110];
    static Queue<Pair> q = new LinkedList();
    static int[] dx = {0, 0, 1, -1};
    static int[] dy = {1, -1, 0, 0};

    public static void main(String[] args) {
        Scanner sca = new Scanner(System.in);
        w = sca.nextInt();
        h = sca.nextInt();
        n = sca.nextInt();
        r = sca.nextInt();
        int i = 0;
        while (n-- > 0) {
            int x = sca.nextInt();
            int y = sca.nextInt();
            q.offer(new Pair(x, y));
            bfs(x, y);
        }
        System.out.println(count+n);
    }

    static void bfs(int x, int y) {
        while (!q.isEmpty()) {
            Pair pair = q.poll();

            for (int i = 0; i < 4; i++) {
                int a = pair.x + dx[i], b = pair.y + dy[i];

                if (a < 0 || a > w || b < 0 || b > h) continue;
                if (st[a][b] || !judge(a, b, x, y)) continue;
                st[a][b] = true;
//                System.out.print(a + " " + b + ",");
                count++;
                q.offer(new Pair(a, b));
            }
        }
    }

    static Boolean judge(int x1, int y1, int x, int y) {
        int dis = (x - x1) * (x - x1) + (y - y1) * (y - y1);
        if (Math.sqrt(dis) <= r) {
            return true;
        }
        return false;
    }
}

class Pair {
    int x, y;

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

到了这里,关于【蓝桥杯】信号覆盖范围——BFS(java题解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 十三届蓝桥杯JAVA B组国赛部分题解

    大学总共参加了三届蓝桥杯,这应该是我最后一次参加蓝桥杯了,再写一篇题解算是给自己的业余竞赛结个尾。我的题解肯定不是最好的,甚至有许多错误,能给大家提供下思路就行。 思路:模拟下时钟就行,签到题 答案:502-8=494(由于匀速运动,59分59秒到0分0秒实际算一次

    2024年02月08日
    浏览(50)
  • 第十五届蓝桥杯 模拟赛第二期java组题解

    一、 问题描述 小蓝要在屏幕上放置一行文字,每个字的宽度相同。 小蓝发现,如果每个字的宽为 36 像素,一行正好放下 30 个字,字符之间和前后都没 有任何空隙。 请问,如果每个字宽为 10 像素,字符之间不包含空隙,一行可以放下多少个字? 答案提交 这是一道结果填空

    2024年02月03日
    浏览(54)
  • 2023年第十四届蓝桥杯省赛Java C组题解

    只做出来(ACDFGH),挑几个出来,答案不一定正确,但自己测试通过了 求1~20230408的和 这里就直接套等差数列的求和公式,答案:204634714038436   【问题描述】         有一个长度为n的数组(n是10的倍数),每个数 Ai 都是区间[0,9]中的整数,小明发现数组里每种数出现的次数不太

    2023年04月26日
    浏览(41)
  • 家用无线路由器如何用网线桥接解决有些房间无线信号覆盖不好的问题(低成本)

    光猫ZXHN F677V9 水星MW325R 无线百兆路由器 100M宽带,2.4G无线网络 苹果手机 安卓平板电脑 三室一厅94平 家用无线路由器如何用网线桥接解决有些房间无线信号不好问题低成本解决,无线覆盖和漫游 主路由器用的运营商的光猫自带无线WiFi 网络箱在主卧,这个光猫在网络箱里,主

    2024年02月07日
    浏览(48)
  • 2023第十四届蓝桥杯模拟赛第二期个人题解(Java实现)

    2023第十四届蓝桥杯校内模拟赛第三期个人题解(Java实现) 蓝桥杯真题——单词分析(Java实现) 这篇文章为个人题解,假如我写的解法有误,欢迎大家在评论区指正👏👏!!!希望这篇文章对你有帮助❤❤ 请找到一个大于 2022 的最小数,这个数转换成二进制之后,最低的

    2023年04月23日
    浏览(166)
  • 第十四届蓝桥杯大赛软件赛省赛 Java 大学 B 组题解

    找规律,可以先手动模拟几次,会发现 随着n越大,零也越多,当n为40的时候刚好有9个0 所以到40项以后的末尾9个阶乘的和一定是不变的,可以用手算,也可以写程序 答案是,901327897 代码: Java中有十进制转化为二进制,十六进制,八进制的方法,暴力枚举一下即可。(因为

    2024年02月02日
    浏览(43)
  • AcWing 24:机器人的运动范围 ← BFS、DFS

    【题目来源】 https://www.acwing.com/problem/content/description/22/ 【题目描述】 地上有一个 m 行和 n 列的方格,横纵坐标范围分别是 0∼m−1 和 0∼n−1。 一个机器人从坐标 (0,0) 的格子开始移动,每一次只能向左,右,上,下四个方向移动一格。 但是不能进入行坐标和列坐标的数位之

    2024年02月14日
    浏览(32)
  • 千寻服务及覆盖范围查询

    千寻跬步-FindM(亚米级高精度定位服务)在设备支持、监测环境良好的情况下,精度可达0.5m左右; 千寻知寸-FindCM(厘米级高精度定位服务)在设备支持、监测环境良好的情况下,精度可达1-5cm左右; 千寻见微-FindMM(静态毫米级高精度定位服务)在设备支持、监测环境良好的

    2024年02月10日
    浏览(44)
  • 蓝桥杯专题之递归+dfs+bfs篇

    2013年:第39级台阶 2014年:李白打酒,地宫取宝 2015年:牌型种数 2016年:方格填数,剪邮票 2018年:全球变暖 2019年:迷宫 2020年:走方格,七段码 2022年模拟赛:2021变1的最短操作数 2022年第一次模拟赛:15级台阶 2022年国赛:扩散 小明刚刚看完电影《第39级台阶》,离开电影院

    2023年04月08日
    浏览(45)
  • 蓝桥杯练习题dfs与bfs

    本文主要是【算法】——dfs与bfs的文章,如果有什么需要改进的地方还请大佬指出⛺️ 🎬作者简介:大家好,我是听风与他🥇 ☁️博客首页:CSDN主页听风与他 🌄每日一句:狠狠沉淀,顶峰相见

    2024年01月21日
    浏览(44)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包