Checkpoints [AtCoder Beginner Contest 057 B]

atcoder.jp

学生の座標n個とチェックポイントの座標m個が与えられ、それぞれの学生をマンハッタン距離で最短のチェックポイントに移動させるときの、そのチェックポイントの番号を出力せよ、という問題です。

200点にしてはずいぶんいやらしい問題……というわけでもなく、ごく普通の問題ですが、今回は練習ついでにオブジェクト指向で記述してみることにしました。

//abc057-b

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	static int mod = 1000000007;
	public static void main(String[] args) {

		int n = sc.nextInt();
		int m = sc.nextInt();
		Point[] student = new Point[n];
		Point[] checkPoint = new Point[m];
		for (int i=0; i<n; i++) student[i] = new Point(sc.nextInt(), sc.nextInt());
		for (int i=0; i<m; i++) checkPoint[i] = new Point(sc.nextInt(), sc.nextInt());

		for (int i=0; i<n; i++) {
			int minNum = -1;
			int minValue = Integer.MAX_VALUE;
			for (int j=0; j<m; j++) {
				int d = calcManhatDistance(student[i].getX(), student[i].getY(), checkPoint[j].getX(), checkPoint[j].getY());
				if (d < minValue) {
					minValue = d;
					minNum = j;
				}
			}
			System.out.println(minNum+1);
		}

	}

	static int calcManhatDistance (int x1, int y1, int x2, int y2) {
		int d = Math.abs(x1-x2)+Math.abs(y1-y2);
		return d;
	}
	static double calcEuclidDistance (double x1, double y1, double x2, double y2) {
		double d = Math.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
		return d;
	}

}



class Point{
	private int x;
	private int y;

	Point(int a, int b) {x=a; y=b;}

	int getX() {return x;}
	int getY() {return y;}
	void setX(int n) {x = n;}
	void setY(int n) {y = n;}
}

まず、座標を格納するためのクラスPointを定義します。迷路を幅優先探索で解く問題など、座標を処理しなければならない問題は多いですから、これを作ってスニペットに登録しておくと便利です。

次に、Point型配列に学生とチェックポイントをそれぞれ格納します。

最後に、それぞれの学生について、マンハッタン距離で最も近いところにあるチェックポイントを調べて、その番号を出力して終了です。マンハッタン距離を計算するために、ここではメソッドを定義しています。マンハッタン距離を求めるメソッドの下に記述してあるのはユークリッド距離を求めるメソッドです。この二つもPointクラスと同様にスニペットに登録してあります。

この記述をもってしてオブジェクト指向と表現していいのか、はたしてわかりませんが、少なくとも私の場合は、多少記述量が増えたとしてもオブジェクト指向でわかりやすく丁寧に書いたほうが正解できる確率が高いみたいです。