问题描述
小蓝负责一块区域的信号塔安装,整块区域是一个长方形区域,建立坐标轴后,西南角坐标为 (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; } }
文章来源:https://www.toymoban.com/news/detail-406671.html
到了这里,关于【蓝桥杯】信号覆盖范围——BFS(java题解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!