位于InsertEdge函数中第二行,用vscode调试时(用的g++编译器)运行到这里时会引发中断,用vs2019调试时(唯一的改动是scanf改为scanf_s显示“***.exe已触发了一个断点。”
vscode调试每一次都会有异常,而vs2019第二次运行时却正常
测试的输入是
14 20
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12
/*Saving James Bond - Easy Version*/
/*使用了邻接表和DFS*/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
const int ISLAND_D = 15;
const int BANK_D = 50;
typedef int Vertex;
typedef struct AdjVNode* PtrToAdjVNode;
struct AdjVNode
{
Vertex AdjV;
PtrToAdjVNode Next;
};
typedef PtrToAdjVNode* AdjList;
struct GNode
{
int Nv;
int Ne;
AdjList G;
};
typedef struct GNode* LGraph;
struct Coordinate
{
float x;
float y;
};
float Distance(struct Coordinate coorA, struct Coordinate coorB)
{
float d = sqrtf(pow((coorA.x - coorB.x), 2) + pow((coorA.y - coorB.y), 2));
return d;
}
LGraph CreateGraph(int N)
{
LGraph Graph = (LGraph)malloc(sizeof(struct GNode));
Graph->Nv = N + 2;
Graph->Ne = 0;
Graph->G = (AdjList)malloc(sizeof((N + 2) * sizeof(PtrToAdjVNode)));
for (int i = 0; i <= N + 1; i++)
{
Graph->G[i] = NULL;
}
return Graph;
}
void InsertEdge(LGraph Graph, Vertex V1, Vertex V2)
{
PtrToAdjVNode NewNode;
NewNode= (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
NewNode->AdjV = V2;
NewNode->Next = Graph->G[V1];
Graph->G[V1] = NewNode;
NewNode = (PtrToAdjVNode)malloc(sizeof(struct AdjVNode));
NewNode->AdjV = V1;
NewNode->Next = Graph->G[V2];
Graph->G[V2] = NewNode;
Graph->Ne++;
}
int DFS(LGraph Graph, Vertex V, int* visited, Vertex BankV)
{
if (V == BankV)
return 1;
visited[V] = 1;
PtrToAdjVNode W= Graph->G[V];
while (W)
{
if (!visited[W->AdjV])
if (DFS(Graph, W->AdjV, visited, BankV))
return 1;
W = W->Next;
}
return 0;
}
int main()
{
int N, D;
scanf("%d %d", &N, &D);
Vertex BankV = N + 1;
struct Coordinate* coordinates = (struct Coordinate*)malloc((N + 1) * sizeof(struct Coordinate));
coordinates[0].x = coordinates[0].y = 0;
for (int i = 1; i <= N; i++)
{
scanf("%f %f", &(coordinates[i].x), &coordinates[i].y);
}
LGraph Graph = CreateGraph(N);
for (int i = 1; i <= N; i++)
{
if (Distance(coordinates[0], coordinates[i]) <= ISLAND_D + D)
InsertEdge(Graph, 0, i);
}
for (int i = 1; i <= N; i++)
{
if (BANK_D - fabsf(coordinates[i].x) <= D)
InsertEdge(Graph, i, BankV);
}
for (int i = 1; i < N; i++)
for (int j = i + 1; j <= N; j++)
{
if (Distance(coordinates[i], coordinates[j]) <= D)
InsertEdge(Graph, i, j);
}
int* visited = (int*)malloc((N + 2) * sizeof(int));
for (int i = 0; i < N + 2; i++)
visited[i] = 0;
if (DFS(Graph, 0, visited, BankV))
printf("Yes");
else
printf("No");
return 0;
}