[AHOI2017初中组] cover
题目背景
以下为不影响题意的简化版题目。
题目描述
一个 \(n\times n\) 的网格图（标号由 \(1\) 开始）上有 \(m\) 个探测器，每个探测器有个探测半径 \(r\) ，问这 \(n\times n\) 个点中有多少个点能被探测到。
输入格式
第一行 \(3\) 个整数 \(n,m,r\)。
接下来 \(m\) 行，每行两个整数 \(x,y\)表示第 \(i\) 个探测器的坐标。
输出格式
能被探测到的点的个数。
样例 #1
样例输入 #1
5 2 1
3 3
4 2
样例输出 #1
8
提示
\(1\le n,m\le 100\)
我的代码
总体思路采用的是暴力枚举，覆盖到的点标记为Exist，否则为NonExist；最后对于整个网格图中的Exist计数
出现过的错误
有两个测试点出现
Runtime Error.Received signal 6: Aborted / IOT trap.
问题一般是：
- 内存错误：例如访问无效的内存地址、堆栈溢出或空指针引用等。这可能是由于未初始化的指针、错误的内存管理或动态内存分配问题引起的。
- 除以零错误：这是指试图将一个数除以零，这在数学运算中是不允许的。当程序执行到一个除法操作，除数为零时，会触发除以零错误。
- 非法指令：当程序执行遇到一个无效或非法的机器指令时，会导致运行时错误。这通常是由于程序错误、损坏的二进制文件或不兼容的硬件引起的。
- 栈溢出：当函数调用的嵌套层次太深，或者在递归函数中没有正确的终止条件时，会导致栈溢出错误。这会耗尽程序的栈空间，导致程序崩溃。
其实是犯了一个非常愚蠢的错误
上面都还记得使用(n+1)*sizeof,这里分配内存的时候却忘记了\((m+1)\times sizeof(Zone)\)，其实上这里i=0->m-1也并无影响，上面使用(n+1)是因为坐标从1开始，将array[i][j]中的i，j看做坐标，从1开始，其实0是浪费掉了的
//第二十七行
Zone *zones = (Zone *)malloc(m * sizeof(Zone));
for (int i = 1; i <= m; i++)
{
scanf("%d %d", &zones[i].x, &zones[i].y);
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define Exist 1
#define NonExist 0
typedef struct zone
{
int x;
int y;
} Zone;
int main()
{
int n, m, r, num = 0;
scanf("%d %d %d", &n, &m, &r);
int **array = (int **)malloc((n + 1) * sizeof(int *));
for (int i = 0; i <= n; i++)
{
array[i] = (int *)malloc((n + 1) * sizeof(int));
memset(array[i], NonExist, (n + 1) * sizeof(int));
}
Zone *zones = (Zone *)malloc(m * sizeof(Zone));
for (int i = 1; i <= m; i++)
{
scanf("%d %d", &zones[i].x, &zones[i].y);
for (int j = 0; j <= n; j++)
{
for (int k = 0; k <= n; k++)
{
if (sqrt(pow(abs(zones[i].x - j), 2) + pow(abs(zones[i].y - k), 2)) <= r)
{
array[j][k] = Exist;
}
}
}
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (array[i][j])
{
num++;
}
}
}
printf("%d", num);
free(array);
free(zones);
return 0;
}
经过GPT修改
1.一个比较好的地方使用了calloc函数，既开辟了空间，又自动赋0，一举两得
grid[i] = (int *)calloc((n + 1), sizeof(int));
2.在我的代码中，我仅仅释放了array，但是并没有释放array[i],这里提醒我了
for (int i = 0; i <= n; i++)
{
free(grid[i]);
}
3.他这里将网格图的横纵坐标放在外面，而对于坐标点嵌套在循环里面，总循环次数是一样的，但是在每个坐标点判断完成后，直接在第二层循环用if判断即可，不需要再遍历一遍网格图，大大节省了时间
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
int detected = 0;
for (int k = 0; k < m; k++)
{
int dx = abs(detectors[k].x - i);
int dy = abs(detectors[k].y - j);
double distance = sqrt(dx * dx + dy * dy);
if (distance <= r)
{
detected = 1;
break;
}
}
if (detected)
{
count++;
grid[i][j] = 1;
}
}
}
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
typedef struct
{
int x;
int y;
} Detector;
int main()
{
int n, m, r;
scanf("%d %d %d", &n, &m, &r);
int **grid = (int **)malloc((n + 1) * sizeof(int *));
for (int i = 0; i <= n; i++)
{
grid[i] = (int *)calloc((n + 1), sizeof(int));
}
Detector *detectors = (Detector *)malloc(m * sizeof(Detector));
for (int i = 0; i < m; i++)
{
scanf("%d %d", &detectors[i].x, &detectors[i].y);
}
int count = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
int detected = 0;
for (int k = 0; k < m; k++)
{
int dx = abs(detectors[k].x - i);
int dy = abs(detectors[k].y - j);
double distance = sqrt(dx * dx + dy * dy);
if (distance <= r)
{
detected = 1;
break;
}
}
if (detected)
{
count++;
grid[i][j] = 1;
}
}
}
printf("%d\n", count);
for (int i = 0; i <= n; i++)
{
free(grid[i]);
}
free(grid);
free(detectors);
return 0;
}