[Java]伯俊/Bam/3190号

[Java]伯俊/Bam/3190号
質問する
ヘビ問題リンク
「Dummy」というドスゲームがありました.このゲームには蛇が這い出していて、りんごを食べると蛇の長さが増えます.ヘビが這い回って、壁や自分の体にぶつかって、ゲームは終わりました.
ゲームはNxN正斜角 碁盤の上で行い,いくつかの格子の上で りんごが置いてあります.板の上下左右端に壁があります.ゲーム開始時、ヘビは一番上の一番左側にあり、ヘビの長さは1です.蛇は最初は右です.
ヘビは毎秒移動し、次のルールに従います.
まずヘビは体長を増やします. 頭. 次のグリッドにあります.

移動した格子の中にリンゴがあれば、格子の中のリンゴは消え、しっぽも動かない.

移動した格子にリンゴがなければ、体の長さを短くして尻尾のある格子を空けます.つまり、身長は変わらない.

リンゴの位置と蛇の移動経路を与えると,このゲームは数秒で終了する.
入力
最初の行は、プレートのサイズNを与える.(2≦N≦100)次の行はリンゴの個数Kを与える.(0 ≤ K ≤ 100)
次のK行はリンゴの位置を示し,1番目の整数は行を表し,2番目の整数は列の位置を表す.りんごの位置が違います.一番上の左側(1行1列)にはりんごがありません.
次の行は蛇の方向転換回数Lを与える.(1 ≤ L ≤ 100)
以下のL行は蛇の方向変換情報を提供し,整数Xと文字Cからなる.ゲーム開始時間からX秒終了後に左(Cは「L」)または右(Cは「D」)に90度回転します.Xは10000以下の正の整数であり、方向変換情報はXが増加する順に与えられる.

6
3
3 4
2 5
5 3
3
3 D
15 L
17 D

しゅつりょく
1行目の出力ゲームは数秒で終了します.

9

方法
実施問題を解決し続けると、頭が砕けてしまうハハ.

重要な部分は2つあります:

ヘビの頭と尾の座標を持ち、リンゴを食べる時と食べない時を条件に、しっぽを動かすかどうかを実現しています.

頭部移動方向と尾部移動方向は密接に関連している.例えば、ヘビの長さが4であると、ヘッド移動方向の4番目の先の方向が現在の尻尾移動方向

となる.

注意事項(多分これのために挿したのでしょう)

もしあなたが

りんごを食べたら、それを取り除くべきです.

によって与えられた操舵時間は、その時間が経過した次の方向を示す.例えば、4秒でL(左方向)であると、4秒後には方向が変化する

となる.

アップルの位置を入力するインデックスは1から

です.
コード#コード#

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main_G5_3190 {

    static int n;
    static int k;
    static List<Apple> apples;
    static int l;
    static List<Snake> snakes;
    static boolean[][] isBody;
    static int headR, headC, tailR, tailC;
    static int[][] deltas = {{0,1},{1,0},{0,-1},{-1,0}};
    static int headDirection;
    static List<Integer> headDirectionList;
    static int tailDirection;
    static int cntSec;
    static int snakeLength;
    static boolean gameOver;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        k = Integer.parseInt(br.readLine());
        // 사과 좌표 입력
        apples = new ArrayList<>();

        for(int i=0;i<k;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            apples.add(new Apple(Integer.parseInt(st.nextToken())-1, Integer.parseInt(st.nextToken())-1));
        }

        // 뱀 방향 정보 입력
        l = Integer.parseInt(br.readLine());
        snakes = new ArrayList<>();

        for(int i=0;i<l;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            snakes.add(new Snake(Integer.parseInt(st.nextToken()), st.nextToken().charAt(0)));
        }

        isBody = new boolean[n][n];
        headR = 0;
        headC = 0;
        tailR = 0;
        tailC = 0;

        // 머리와 꼬리 둘다 우측방향
        headDirection = 0;
        tailDirection = 0;

        // 0,0에서 시작
        snakeLength = 1;
        isBody[0][0] = true;
        cntSec = 0;
        headDirectionList = new ArrayList<>();
        while(!gameOver){
            simulate();
        }

        System.out.println(cntSec);

    }

    public static void simulate(){
        cntSec++;
        //System.out.print("head : " + headR + ", " + headC + " tail : " + tailR + ", " + tailC + " -> " );

        // 머리 이동
        int nextHeadR = headR + deltas[headDirection][0];
        int nextHeadC = headC + deltas[headDirection][1];

        // 벽에 부딪히거나 몸에 부딪히면 게임 끝
        if(nextHeadR < 0 || nextHeadC >= n || nextHeadC < 0 || nextHeadR >= n || isBody[nextHeadR][nextHeadC]) {
            gameOver = true;
            return;
        }

        // 머리이동
        headR = nextHeadR;
        headC = nextHeadC;
        isBody[headR][headC] = true;

        // 머리 부분에 사과가 있으면 꼬리 안움직이고 없으면 움직임
        boolean isApple = false;
        for (Apple apple : apples){
            if(apple.r == headR && apple.c == headC){
                isApple = true;
                apples.remove(apple);
                break;
            }
        }

        // 사과 있으면 꼬리 안움직이고 현재 길이를 늘림
        if(isApple) {
            snakeLength += 1;
        }
        // 사과 없으면 꼬리를 움직임
        else{

            int nextTailR = tailR + deltas[tailDirection][0];
            int nextTailC = tailC + deltas[tailDirection][1];
            isBody[tailR][tailC] = false;
            tailR = nextTailR;
            tailC = nextTailC;

        }

        // head의 다음 방향 찾기
        for(Snake snake : snakes){
            if(snake.sec == cntSec){
                if(snake.direction == 'D') headDirection = (headDirection + 1) % 4;
                else if(snake.direction == 'L') headDirection = (headDirection + 3) % 4;
            }
        }
        headDirectionList.add(headDirection);

        // tail의 다음 방향 찾기  ( 꼬리 방향은 머리 방향보다 뱀 길이만큼 느리다 !! )
        tailDirection = headDirectionList.get(Math.max(0,cntSec - snakeLength ));

        //System.out.println("head : " + headR + ", " + headC + " tail : " + tailR + ", " + tailC + " sec : " + cntSec);

    }

    public static class Apple{
        public int r;
        public int c;
        Apple(int r, int c){
            this.r = r;
            this.c = c;
        }
    }

    public static class Snake{
        public int sec;
        public char direction;

        Snake(int sec, char direction){
            this.sec = sec;
            this.direction = direction;
        }
    }
}