找到最近的NPC

[编程题]找到最近的NPC

热度指数：1712 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

在2D游戏的一张地图中随机分布着n个NPC，玩家君莫笑进入地图时随机出生在了一个坐标（x,y）。请找到距离玩家最近的NPC。假设地图大小为128*128，NPC和玩家均不能出现在地图外面。

输入描述:

参数一：整形，玩家出生坐标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个

算法知识视频讲解

Java

lmz9509

/*
思路：循环遍历的方式，建立一个二维数组，存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)

Java

何止hz

无语，我是看不出那里有可能数组越界。。。。

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)