Pilot's Blog
0%

枚举-安全区

发表于 更新于 分类于 ， ， Valine：
本文字数： 1.1k 阅读时长 ≈ 1 分钟
枚举问题，一般都很暴力

题目

题目描述

在一个nn的网格图上有m个探测器，第i个探测器位于(xi,yi)位置，探测半径为ri。 求出nn个点中有多少个是安全的点，即未被探测的点。

输入格式

第一行为两个整数n,m(1<=n<=100,1<=m<=n*n) 接下来m行每行3个整数表示xi,yi,ri（1<=xi,yi,ri<=n）

输出格式

输出一个整数表示答案

输入样例

1
2
3
5 2
3 3 1
4 2 1

输出样例

1
17

分析：

每得到一个点，就遍历所有二维矩阵，判断二维矩阵中对应的点与探测点核心距离是否小于探测距离

利用isVisited数组判断是否访问过，防止重复计数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.Scanner;
public class Main {
    public static double distance(int x1, int y1, int x2, int y2) {
        return Math.hypot((x1 - x2), (y1 - y2));
    }
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();
        boolean[][] data = new boolean[n + 1][n + 1];
        for(int i = 0; i < n + 1; i++) {
            for(int j = 0; j < n + 1; j++) data[i][j] = true;
        }
        int totalNum = n * n;
        for(int i = 0; i < m; i++) {
            int xi = input.nextInt();
            int yi = input.nextInt();
            int ri = input.nextInt();
            for(int otherX = 1; otherX <= n; otherX++) {
                for(int otherY = 1; otherY <= n; otherY++) {
                    double dis = distance(xi, yi, otherX, otherY);
                    if(dis <= (double)ri && data[otherX][otherY] == true) {
                        data[otherX][otherY] = false;
                        totalNum--;
                    }  //if
                }   //for
            }   //for
        }   //for
        System.out.println(totalNum);
        input.close();
    }    
}