在2D游戏的一张地图中随机分布着n个NPC,玩家君莫笑进入地图时随机出生在了一个坐标(x,y)。请找到距离玩家最近的NPC。假设地图大小为128*128,NPC和玩家均不能出现在地图外面。
在2D游戏的一张地图中随机分布着n个NPC,玩家君莫笑进入地图时随机出生在了一个坐标(x,y)。请找到距离玩家最近的NPC。假设地图大小为128*128,NPC和玩家均不能出现在地图外面。
参数一:整形,玩家出生坐标x
参数二:整形,玩家出生坐标y
参数三:整形,NPC数量n
参数四:NPC二维坐标数组的一维表示,使用字符串形式传入,注意逗号前后不要加空格,比如地图中有两个NPC,坐标分别是(32,33)和(25,25),则此处传入32,33,25,25
查询到的NPC坐标,注意坐标值前后有圆括号
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); }
/* 思路:循环遍历的方式,建立一个二维数组,存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 + ")"); } }*/
#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; }
#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; }题本身没啥逻辑难度,就是考一手字符串的处理,加油!
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(); } }
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]))
#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; }