(BOJ)ビールを飲みながら9205号を歩く

質問する

https://www.acmicpc.net/problem/9205

質問する

松島に住んでいる尚根さんと友達は松島で行われるPentaPortRock祭りに行きます.今年はビールを飲みながら歩くことにしました.出発は尚勤家で、ビールを一箱持って出発.1箱のビールには20個のビールがある.喉が渇いていないので、50メートルごとに1本飲むつもりです.つまり、50メートル歩く前にビールを1本飲むということです.
尚根の家で祭りをするところは遠いです.そのため、もっとビールを買う必要があるかもしれません.事前にネットで調べていたら、幸いビールを売っているコンビニがありました.コンビニに入る時、空き瓶を捨てて新しいビール瓶を買うことができます.しかし、箱の中のビールは20本を超えてはいけません.コンビニを出て50 m歩く前にもビールを1本.
コンビニ、上根家、ペンシルベニア港ロックフェスティバルの座標です.サンゲンと友達が幸せに祭りに着くかどうか、番組を作ってみましょう.

入力

第1行は、試験例の個数tを与える.(t ≤ 50)
各テストボックスの最初の行には、ビールを売っているコンビニの数nが与えられています.(0 ≤ n ≤ 100).
次のn+2行は、上根家、コンビニ、PentaPortrock Festival座標を与えます.各座標は2つの整数xとyからなる.(両方ともm,−32768≦x,y≦32767)
松島は長方形の町です.2つの座標間の距離は、x座標の差+y座標の差である.(マンハッタン通り)

しゅつりょく

各テストボックスについて、尚根と友人たちが幸せに祭りに行くことができれば、「happy」、中間ビールが切れて移動できない場合は「sad」を出力します.

に近づく

BFSアクセスが使用されており、アクセスの頂点については、コンビニリストから座標を削除する方向にリストで実装されています.
まず家に座標ノードを追加します.

q.add(home);

BFS実装時に主に使用するキューを使用した.
現在行列から取り出されている家やコンビニを基準に、祭りやコンビニは50*20=1000 m以内でなければなりません.
1.1キロ以内に祭りがあります
幸せに終わる
2.1 km以内にコンビニがございます
コンビニの座標をキューに入れます.

while (!q.isEmpty()) {
	Node node = q.poll();

    int x = node.x;
    int y = node.y;

    if (Math.abs(festival.x - x) + Math.abs(festival.y - y) < 50 * 20
        || Math.abs(festival.x - x) + Math.abs(festival.y - y) == 50 * 20) {
        	isHappy = true;
            	break;
    }

    for (int j = 0; j < list.size(); j++) {
    	Node store = list.get(j);

        if ((Math.abs(store.x - x) + Math.abs(store.y - y) < 50 * 20)
            || Math.abs(store.x - x) + Math.abs(store.y - y) == 50 * 20) {
            	q.add(store);
                list.remove(j--);
        }
    }
}

コード#コード#

import java.util.*;
import java.util.Queue;

public class Main {
    static class Node {
        int x;
        int y;
        Node (int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);

        int t = scan.nextInt();

        for (int i = 0; i < t; i++){
            int n = scan.nextInt();
            Node home = null;
            Node festival = null;
            boolean isHappy = false;
            ArrayList<Node> list = new ArrayList<>();
            Queue<Node> q = new LinkedList<>();

            for (int j = 0; j < n + 2; j++) {
                int x = scan.nextInt();
                int y = scan.nextInt();

                if (j == 0) {
                    // 집
                    home = new Node(x, y);
                } else if (j == n + 1) {
                    // 축제
                    festival = new Node(x, y);
                } else {
                    // 편의점
                    Node node = new Node(x, y);
                    list.add(node);
                }
            }

            q.add(home);

            while (!q.isEmpty()) {
                Node node = q.poll();

                int x = node.x;
                int y = node.y;

                if (Math.abs(festival.x - x) + Math.abs(festival.y - y) < 50 * 20
                        || Math.abs(festival.x - x) + Math.abs(festival.y - y) == 50 * 20) {
                    isHappy = true;
                    break;
                }

                for (int j = 0; j < list.size(); j++) {
                    Node store = list.get(j);

                    if ((Math.abs(store.x - x) + Math.abs(store.y - y) < 50 * 20)
                            || Math.abs(store.x - x) + Math.abs(store.y - y) == 50 * 20) {
                        q.add(store);
                        list.remove(j--);
                    }
                }
            }

            if (isHappy) {
                System.out.println("happy");
            } else {
                System.out.println("sad");
            }
        }
    }
}

実は先日c++で実現しました.これにより距離計算部の条件が実現される.

50で割った場合、残りが発生すると少し差(?)が出ます.コンビニや祭りには行けないので、このまま実現してしまったので、再実現後、残りのことを考える必要はありません.