リンク

質問リンク

問題の説明

「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が増加する順に与えられる.

しゅつりょく

1行目の出力ゲームは数秒で終了します.

I/O例

に答える

ヘビの方向変換情報を含むInfoオブジェクトと、ヘビの位置を含むPosオブジェクトを宣言します.

方向は時計回り方向であり、dx[4]とdy[4]を東(0)南(1)西(2)北(3)で表す.

問のすべての入力を受けた場合、Info配列の最後にinfo(10001,info[i].dir)を配列に入れ、位置変換を行わなければ壁に釘付けになるまで元の道で行います.

蛇の活動はこのように体現されている.
4-1. 追加・削除を容易にするため,ヘビの位置情報を接続リストとして管理する.
4-2. ヘビの頭の部分をdir方向に1格ずつ行います.
4-3. 頭が自分の体にぶつかった場合(snake.contains()または壁にぶつかった場合(out range())、現在の時間に1を加えて出力して終了します.
4-4. 4-3番のコースに合格したら、最初の尾を外します.次にヘアを追加します.
4-5. この過程でりんごを食べたら、取り除いたしっぽを最初に追加します.
4-6. time++

変換方向

このような実現問題はcotteによく現れるが,これを解くのに長い時間がかかった.
しかし、久しぶりに学部生の時に真剣に連絡リストを書いたので、ちょっと不思議で、思い出もありました.
でも一度はこのように解いて自信を感じました!

コード#コード#

package Sample;
import java.util.*;
class Info{
	int second;
	String dir;
	Info(int second, String dir) {
		this.second = second;
		this.dir = dir;
	}
}
class Pos {
	int x, y;
	Pos(int x, int y) {
		this.x = x;
		this.y = y;
	}
	@Override
	public boolean equals(Object obj) {
		return this.x == ((Pos) obj).x && this.y == ((Pos) obj).y;
	}
}
public class Main {
	static boolean[][] map;
	static int[] dx = {0, 1, 0, -1};
	static int[] dy = {1, 0, -1, 0};
	public static boolean Out_range(int x, int y, int N) {
		return !(x >= 1 && x <= N && y >= 1 && y <= N);
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		map = new boolean[N + 1][N + 1];
		for(int i = 0; i < K; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			map[x][y] = true;
		}
		int L = sc.nextInt();
		Info[] info = new Info[L + 1];
		for(int i = 0; i < L; i++) {
			int second = sc.nextInt();
			String s = sc.next();
			info[i] = new Info(second, s);
		}
		int time = 0;
		int dir = 0;
		LinkedList<Pos> snake = new LinkedList<>();
		snake.add(new Pos(1,1));
		for(int i = 0; i < info.length; i++) {
			
			while(time < info[i].second) {
				Pos p = snake.getLast();
				int nx = p.x + dx[dir];
				int ny = p.y + dy[dir];
				if(snake.contains(new Pos(nx, ny)) || Out_range(nx,ny,N))
				{
					System.out.println(time + 1);
					return ;
				}
				Pos remov = snake.removeFirst();
				snake.add(new Pos(nx, ny));
				if(map[nx][ny]) {
					snake.add(0, remov);
					map[nx][ny] = false;
				}
				time++;
			}
			if(info[i].dir.equals("D"))
				dir = (dir + 1) % 4;
			else {
				if(dir == 0) 
					dir = 3;
				else
					dir = (dir - 1) % 4;
			}
			if(i == info.length - 2) 
				info[i + 1] = new Info(10001, info[i].dir);
		}
	}
}