在2D游戏的一张地图中随机分布着n个NPC，玩家君莫笑进入地图时随机出生在了一个坐标（x,y）。请找到距离玩家最近的NPC。假设地图大小为128*128，NPC和玩家均不能出现在地图外面。
[编程题]找到最近的NPC
- 热度指数：1712 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
参数一：整形，玩家出生坐标x
参数二：整形，玩家出生坐标y
参数三：整形，NPC数量n
参数四：NPC二维坐标数组的一维表示，使用字符串形式传入，注意逗号前后不要加空格，比如地图中有两个NPC，坐标分别是(32,33)和(25,25)，则此处传入32,33,25,25
输出描述:
查询到的NPC坐标，注意坐标值前后有圆括号
示例1
输入
32,48,3,33,40,40,50,32,45
输出
(32,45)
备注:
NPC数量不超过1000个
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <errno.h>
#define NOT !
#define NPC 2
typedef enum { UNKNOW = 0, OK = 1, ERROR = -1, MEMORY_OVERFLOW = -2 } Status;
typedef struct Coordinate {
int x;
int y;
} Coord;
// ==================== 链式队列存储结构表示与实现 ====================
typedef Coord QElemType;
typedef struct QNode {
QElemType data; // 链式队列节点的数据域
struct QNode* next; // 链式队列节点的指针域
} QNode, *PQNode;
typedef struct {
PQNode front; // 教材上front “始终” 指向头节点，而非首元节点
PQNode rear;
size_t length;
} LinkQueue;
Status InitQueue(LinkQueue* Q) {
if (!((*Q).front = (PQNode) calloc(1, sizeof(QNode)))) { // may be no enough space!
fprintf(stderr, "InitQueue Memory Overflow: %s\n", strerror(errno));
exit(MEMORY_OVERFLOW);
}
(*Q).rear = (*Q).front;
(*Q).length = 0;
return OK;
}
bool QueueEmpty(LinkQueue* Q) {
return (*Q).length == 0;
}
size_t QueueLength(LinkQueue* Q) {
return (*Q).length;
}
Status EnQueue(LinkQueue* Q, QElemType e) {
PQNode new_node = (PQNode) calloc(1, sizeof(QNode));
if (!new_node) { // may be no enough space!
fprintf(stderr, "EnQueue Memory Overflow: %s\n", strerror(errno));
exit(MEMORY_OVERFLOW);
}
(*new_node).data = e;
(*Q).rear = (*((*Q).rear)).next = new_node;
++(*Q).length;
return OK;
}
Status DeQueue(LinkQueue* Q, QElemType* e) {
if (QueueEmpty(Q)) {
fputs("DeQueue ERROR: The Queue is empty!\n", stderr);
return ERROR;
}
PQNode node_to_delete = (*(*Q).front).next;
*e = (*node_to_delete).data;
(*(*Q).front).next = (*node_to_delete).next;
if (!(*(*Q).front).next)
(*Q).rear = (*Q).front;
free(node_to_delete);
--(*Q).length;
return OK;
}
QElemType GetFront(LinkQueue* Q) {
if (QueueEmpty(Q)) {
fputs("DeQueue ERROR: The Queue is empty!\n", stderr);
return (Coord) {-1, -1};
}
return (*(*(*Q).front).next).data;
}
Status DestroyQueue(LinkQueue* Q) {
PQNode p = (*Q).front, next;
while (p) {
next = (*p).next;
free(p);
p = next;
}
(*Q).front = (*Q).rear = NULL;
return OK;
}
// ==================== 链式队列存储结构表示与实现 ====================
// ==================== memory static area ====================
const int N = 130; // 内存全局区，一般用来存放全局变量或静态变量
int board[N][N];
// ==================== memory static area ====================
// ==================== Function Prototype (函数原型区) ====================
void breadth_first_search_algorithm(const int sx, const int sy);
// ==================== Function Prototype ====================
int main(const int argc, const char* argv[]) {
int x, y, n;
fscanf(stdin, "%d,%d,%d", &y, &x, &n);
int tx, ty;
while (n--) {
fscanf(stdin, ",%d,%d", &ty, &tx);
*(*(board + ty) + tx) = NPC; // NPC
}
breadth_first_search_algorithm(x, y);
return 0;
}
void breadth_first_search_algorithm(const int sx, const int sy) {
usleep(900 * 1000);
LinkQueue Q;
InitQueue(&Q);
EnQueue(&Q, (Coord) {.x = sx, .y = sy});
*(*(board + sy) + sx) = 1; // mark as visited
static const int dirs[] = { 0, -1, 0, 1, 0 }; // 存放在全局区
Coord coord;
int i, x, y, nx, ny;
while (NOT QueueEmpty(&Q)) {
DeQueue(&Q, &coord);
x = coord.x, y = coord.y;
for (i = 0; i < 4; ++i) {
nx = x + *(dirs + i), ny = y + *(dirs + i + 1);
if (nx < 0 || ny < 0 || nx == 127 || ny == 127 || *(*(board + ny) + nx) == 1)
continue;
if (*(*(board + ny) + nx) == NPC) { // 找到了解
fprintf(stdout, "(%d,%d)", ny, nx);
DestroyQueue(&Q); // 把堆内存还给操作系统
return;
}
EnQueue(&Q, (Coord) {.x = nx, .y = ny});
*(*(board + ny) + nx) = 1;
}
}
DestroyQueue(&Q);
}
发表于 2021-07-16 10:57:49
回复(0)
/*
思路：循环遍历的方式，建立一个二维数组，存NPC坐标，给出一个下标标记实时更新最短距离的下标
或者不用数组存储，直接用两个变量短暂存储
*/
/*
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(",");
int x = Integer.parseInt(str[0].trim());
int y = Integer.parseInt(str[1].trim());
int n = Integer.parseInt(str[2].trim());
int min = Integer.MAX_VALUE;
int index = 0;
int[][] arr = new int[n][2];
for(int i = 0,j=i+3;i<n;i++){
arr[i][0] = Integer.parseInt(str[j].trim());
arr[i][1] = Integer.parseInt(str[j+1].trim());
j = j+2;
int temp = Math.abs(arr[i][0] - x) + Math.abs(arr[i][1] - y);
if(min > temp){
index = i;
min = temp;
}
}
System.out.println("(" + arr[index][0] + "," + arr[index][1] + ")");
}
}*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main{
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] str = br.readLine().split(",");
if (str.length < 4) {
return;
}
int x = Integer.parseInt(str[0].trim());
int y = Integer.parseInt(str[1].trim());
int n = Integer.parseInt(str[2].trim());
int min = Integer.MAX_VALUE;
int a = 0, b = 0;
for(int i = 3;i<n*2+3;i+=2){
int na = Integer.parseInt(str[i].trim());
int nb = Integer.parseInt(str[i+1].trim());
int temp = Math.abs(na - x) + Math.abs(nb - y);
if(min > temp){
a = na;
b = nb;
min = temp;
}
}
System.out.println("(" + a + "," + b + ")");
}
}
/*
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s = br.readLine().split(",");
if (s.length < 4) {
return;
}
int x = Integer.parseInt(s[0].trim());
int y = Integer.parseInt(s[1].trim());
int n = Integer.parseInt(s[2].trim());
double min = Integer.MAX_VALUE;
int nx = 0, ny = 0;
for (int i = 3; i < n * 2 + 3; i += 2) {
int a = Integer.parseInt(s[i].trim());
int b = Integer.parseInt(s[i + 1].trim());
double c = Math.abs(x - a) + Math.abs(y - b);
if (min > c) {
nx = a;
ny = b;
min = c;
}
}
System.out.println("(" + nx + "," + ny + ")");
}
}*/
发表于 2020-05-21 14:52:29
回复(0)
#include <bits/stdc++.h>
using namespace std;
int main(){
int x,y,n;
scanf("%d,%d,%d", &x, &y, &n);
int a,b,px,py;
double Min = INT_MAX, d;
for(int i=0;i<n;i++){
scanf(",%d,%d", &a, &b);
d = sqrt(pow(a-x,2)+pow(b-y,2));
if(d < Min){
Min = d;
px = a;
py = b;
}
}
printf("(%d,%d)\n", px, py);
return 0;
}
发表于 2019-10-18 01:05:16
回复(2)
#include<time.h>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100;
typedef struct Player
{
int x;
int y;
}Player;
typedef struct NPC
{
int x;
int y;
}NPC;
int main()
{
int T;
Player jmx;
NPC* p[N]{nullptr};
cin >> jmx.x;
cin.get();
cin >> jmx.y;
cin.get();
cin >> T;
cin.get();
for (int i=T,j=1; i != 0; i--,j++)
{
p[j] = new NPC;
cin >> p[j]->x;
cin.get();
cin >> p[j]->y;
cin.get();
}
int dist,mindist=2*128*128,minindex=-1;
for (int i = 1; i <= T; i++)
{
dist = (jmx.x-p[i]->x)* (jmx.x - p[i]->x)+(jmx.y-p[i]->y)* (jmx.y - p[i]->y);
if (dist<mindist)
{
mindist = dist;
minindex = i;
}
}
cout << "(" << p[minindex]->x <<"," << p[minindex]->y << ")" << endl;
for (int i = 1; i <= T; i++)
{
delete p[i];
}
return 0;
}
#include<iostream>
#include<cstring>
using namespace std;
const int N = 100;
typedef struct Player
{
int x;
int y;
}Player;
typedef struct NPC
{
int x;
int y;
}NPC;
int main()
{
int T;
Player jmx;
NPC* p[N]{nullptr};
cin >> jmx.x;
cin.get();
cin >> jmx.y;
cin.get();
cin >> T;
cin.get();
for (int i=T,j=1; i != 0; i--,j++)
{
p[j] = new NPC;
cin >> p[j]->x;
cin.get();
cin >> p[j]->y;
cin.get();
}
int dist,mindist=2*128*128,minindex=-1;
for (int i = 1; i <= T; i++)
{
dist = (jmx.x-p[i]->x)* (jmx.x - p[i]->x)+(jmx.y-p[i]->y)* (jmx.y - p[i]->y);
if (dist<mindist)
{
mindist = dist;
minindex = i;
}
}
cout << "(" << p[minindex]->x <<"," << p[minindex]->y << ")" << endl;
for (int i = 1; i <= T; i++)
{
delete p[i];
}
return 0;
}
发表于 2022-09-02 15:56:02
回复(0)
#include<bits/stdc++.h>
using namespace std;
double get_dis(const double &x,const double &y,const double &x1,const double &y1)
{
return sqrt(pow(x-x1,2)+pow(y-y1,2));
}
int main()
{
int x,y,n,xz,yz,xjg,yjg;
double dis,minn=0x3f3f3f3f;
scanf("%d,%d,%d,",&x,&y,&n);
string s,t;cin>>s;
vector<int> v;
while(!s.empty())
{
int sum=0;
while(isdigit(s[sum])) sum++;
t=s.substr(0,sum);
xz=stoi(t);
s.erase(0,++sum); sum=0;
while(isdigit(s[sum])) sum++;
t=s.substr(0,sum);
yz=stoi(t);
s.erase(0,++sum);
double aa=minn;
minn=min(get_dis(xz,yz,x,y),minn);
if(minn!=aa) {xjg=xz;yjg=yz;}
}
cout<<"("<<xjg<<","<<yjg<<")"<<endl;
} 题本身没啥逻辑难度，就是考一手字符串的处理，加油！
发表于 2022-01-12 04:46:15
回复(0)
#include<iostream>
#include<vector>
using namespace std;
class actor{
public:
int x, y;
actor(int a,int b):x(a),y(b){};
actor(){x=0;y=0;}
int length(actor* npc)
{
int x1=this->x - npc->x;
int y1=this->y - npc->y;
return (x1*x1+y1*y1);
}
};
actor FUNA(int x, int y, int n)
{
actor you(x, y);
vector<actor>npc;
vector<int> vt(n, 0);
int min;
int Num;
for (int i = 0; i < n; i++)//创造n个npc
{
cin >> x >> y;
npc.push_back( actor(x, y));
vt[i] = npc[i].length(&you);
}
min = vt[0];
for (int i = 0; i < n; i++)
{
if (min >= vt[i]) Num = i;
}
return npc[Num];
}
int main (void)
{
int x,y,n;
cin >>x>>y>>n;
if(x>128||y>128||x<0||y<0)
return -1;
class actor npc =FUNA(x,y,n);
cout<<'('<<npc.x<<','<<npc.y<<')';
#include<vector>
using namespace std;
class actor{
public:
int x, y;
actor(int a,int b):x(a),y(b){};
actor(){x=0;y=0;}
int length(actor* npc)
{
int x1=this->x - npc->x;
int y1=this->y - npc->y;
return (x1*x1+y1*y1);
}
};
actor FUNA(int x, int y, int n)
{
actor you(x, y);
vector<actor>npc;
vector<int> vt(n, 0);
int min;
int Num;
for (int i = 0; i < n; i++)//创造n个npc
{
cin >> x >> y;
npc.push_back( actor(x, y));
vt[i] = npc[i].length(&you);
}
min = vt[0];
for (int i = 0; i < n; i++)
{
if (min >= vt[i]) Num = i;
}
return npc[Num];
}
int main (void)
{
int x,y,n;
cin >>x>>y>>n;
if(x>128||y>128||x<0||y<0)
return -1;
class actor npc =FUNA(x,y,n);
cout<<'('<<npc.x<<','<<npc.y<<')';
}
这个我在vs上运行是没问题的，在牛客网上就段错误，有没有大佬告诉下为什么
发表于 2021-11-02 13:56:08
回复(0)
无语，我是看不出那里有可能数组越界。。。。
import java.util.Scanner;
/**
* @Author: coderjjp
* @Date: 2020-05-12 21:40
* @Description: 找到最近的NPC
* @version: 1.0
*/
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] split = sc.nextLine().split(",");
int x = Integer.parseInt(split[0]), y = Integer.parseInt(split[1]);
int n = Integer.parseInt(split[2]);
int distance = Integer.MAX_VALUE, cur_distance;
int ans_x = 0, ans_y = 0, cur_x, cur_y;
for (int index = 3; index < split.length; index = index + 2){
cur_x = Integer.parseInt(split[index]);
cur_y = Integer.parseInt(split[index + 1]);
cur_distance = (cur_x - x) * (cur_x - x) + (cur_y - y) * (cur_y - y);
if (cur_distance < distance){
distance = cur_distance;
ans_x = cur_x;
ans_y = cur_y;
}
}
System.out.println("(" + ans_x + "," + ans_y + ")");
sc.close();
}
}
发表于 2020-05-12 22:11:56
回复(1)
#include <iostream>
#include <math.h>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef unsigned int uint;
typedef struct npc_location{
int x;
int distance;
int y;
}NpcLocation;
void get_player_location_and_Npc_num(char *arguments,NpcLocation *player,int *npc_count)
{
player->x = stoi(strtok(arguments,","));
player->y = stoi(strtok(NULL,","));
player->distance = 0;
*npc_count = stoi(strtok(NULL,","));
}
int main()
{
char * arguments = (char *)malloc(8*128*128);
NpcLocation player;
int count_of_npc;
NpcLocation * Npcs = (NpcLocation *)malloc((128*128-1)*sizeof(NpcLocation));
NpcLocation current_npc;
cin >> arguments;
get_player_location_and_Npc_num(arguments,&player,&count_of_npc);
NpcLocation NPC;
for(int i = 0 ;i < count_of_npc; ++i)
{
NPC.x = stoi(strtok(NULL,","));
NPC.y = stoi(strtok(NULL,","));
NPC.distance = pow(player.x-NPC.x,2) + pow(player.y - NPC.y,2);
Npcs[i] = NPC;
}
current_npc = Npcs[0];
for(int i = 1; i < count_of_npc;++i)
{
if(Npcs[i].distance < current_npc.distance)
current_npc = Npcs[i];
}
cout << '(' <<current_npc.x << ',' << current_npc.y << ')' << endl;
free(arguments);
free(Npcs);
return 0;
}
为什么我的数组越界啊?求大佬解答
#include <math.h>
#include <string>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
using namespace std;
typedef unsigned int uint;
typedef struct npc_location{
int x;
int distance;
int y;
}NpcLocation;
void get_player_location_and_Npc_num(char *arguments,NpcLocation *player,int *npc_count)
{
player->x = stoi(strtok(arguments,","));
player->y = stoi(strtok(NULL,","));
player->distance = 0;
*npc_count = stoi(strtok(NULL,","));
}
int main()
{
char * arguments = (char *)malloc(8*128*128);
NpcLocation player;
int count_of_npc;
NpcLocation * Npcs = (NpcLocation *)malloc((128*128-1)*sizeof(NpcLocation));
NpcLocation current_npc;
cin >> arguments;
get_player_location_and_Npc_num(arguments,&player,&count_of_npc);
NpcLocation NPC;
for(int i = 0 ;i < count_of_npc; ++i)
{
NPC.x = stoi(strtok(NULL,","));
NPC.y = stoi(strtok(NULL,","));
NPC.distance = pow(player.x-NPC.x,2) + pow(player.y - NPC.y,2);
Npcs[i] = NPC;
}
current_npc = Npcs[0];
for(int i = 1; i < count_of_npc;++i)
{
if(Npcs[i].distance < current_npc.distance)
current_npc = Npcs[i];
}
cout << '(' <<current_npc.x << ',' << current_npc.y << ')' << endl;
free(arguments);
free(Npcs);
return 0;
}
为什么我的数组越界啊?求大佬解答
发表于 2019-11-22 21:34:38
回复(0)
from queue import Queue
def check(pos):
if -1 < pos[0] < 128 and -1 < pos[1] < 128:
return True
else:
return False
def bfs_search(born_pos: list, npc_pos: list):
dis = [[1024 for _ in range(128)] for _ in range(128)]
if born_pos in npc_pos:
return 0
queue = Queue()
queue.put(born_pos)
dis[born_pos[0]][born_pos[1]] = 0
x = [0, 0, 1, -1]
y = [1, -1, 0, 0]
while not queue.empty():
pos = queue.get()
if pos in npc_pos:
return pos
for i in range(4):
new_pos = [pos[0] + x[i], pos[1] + y[i]]
if check(new_pos) and dis[new_pos[0]][new_pos[1]] == 1024:
dis[new_pos[0]][new_pos[1]] = dis[pos[0]][pos[1]] + 1
queue.put(new_pos)
if __name__ == '__main__':
inputs = list(map(int, input().split(',')))
x, y = inputs[0], inputs[1]
npc_info = inputs[3:]
npc = [[npc_info[2 * i], npc_info[2 * i + 1]] for i in range(len(npc_info) // 2)]
pos = bfs_search([x, y], npc)
print("({},{})".format(pos[0], pos[1]))
发表于 2019-10-18 19:40:46
回复(0)
C++这道题输入时真的坑啊
#include<iostream>
#include<vector>
#include<sstream>
#include<climits>
#include<string>
using namespace std;
int main()
{
vector<int> vec;
string str;
string temk;
while(cin >> temk)
{
str += temk;
}
stringstream stream(str);
string tem;
while(getline(stream, tem, ','))
{
vec.push_back(stoi(tem));
}
int res = INT_MAX;
int x = vec[0];
int y = vec[1];
int left = -1;
int right = -1;
for(int i = 3; i < vec.size();i+=2)
{
int len = abs(x-vec[i]) + abs(y-vec[i+1]);
if(res > len)
{
res = len;
left = vec[i];
right = vec[i+1];
}
}
cout << "(" << left << "," << right << ")" << endl;
return 0;
}
发表于 2019-08-13 20:54:17
回复(1)
感觉就是输入有点坑，其他都还好
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(int argc, char const *argv[])
{
int x,y;
int n;
int x1,y1;
scanf("%d,%d,",&x,&y);
scanf("%d",&n);
int x2,y2;
int distance = 128 * 128;
for(int i=0;i<n;i++){
scanf(",%d,%d",&x1,&y1);
int len = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);
if(len < distance){
distance = len;
x2 = x1;
y2 = y1;
}
}
cout<<"("<<x2<<","<<y2<<")"<<endl;
system("pause");
return 0;
}
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(int argc, char const *argv[])
{
int x,y;
int n;
int x1,y1;
scanf("%d,%d,",&x,&y);
scanf("%d",&n);
int x2,y2;
int distance = 128 * 128;
for(int i=0;i<n;i++){
scanf(",%d,%d",&x1,&y1);
int len = (x1 - x) * (x1 - x) + (y1 - y) * (y1 - y);
if(len < distance){
distance = len;
x2 = x1;
y2 = y1;
}
}
cout<<"("<<x2<<","<<y2<<")"<<endl;
system("pause");
return 0;
}
发表于 2019-07-20 16:53:11
回复(1)
问题信息
通过挑战的用户
查看代码-
2022-09-22 20:29:55 -
2022-09-03 19:54:02
-
2022-09-03 16:25:53
-
2022-09-03 16:09:57
-
2022-09-03 15:43:00
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
