新しいゲーム2(17837)

1.質問

質問リンク
説明:
ヒョンは周囲を見ながら碁盤とマレーで新しいゲームを作ることにした.新しいゲームサイズはN×Nチェス盤で行い、使用する馬の個数はK個です.馬は原版で、1匹はすぐに別の馬を置くことができます.チェス盤の各コマは白、赤、青の1つに塗られている.
ゲームは碁盤にK頭馬を乗せてから始まります.馬は1番からK番まで番号があり、移動方向も予め決まっています.移動方向は、上、下、左、右の4つのいずれかです.
一回のターンは1番馬からK番馬の順に移動します.1頭の馬が移動すると、上の馬も一緒に移動します.馬の移動方向の欄によって、馬の移動は以下のように異なります.回転中に4つ以上の馬を積んだ瞬間、ゲームは終了.

A号馬が移動する車両

ホワイトの場合は、セルに移動します.移動するセルにすでに馬がいる場合は、A番馬を一番上に置きます.

A番馬の上に他の馬がいるとA番馬と上のすべての馬が移動します.

例えば、

は、A、B、Cに積まれており、移動するセルにD、Eがあれば、A番馬が移動するとD、E、A、B、Cとなる.

赤の場合は、移動後にA番馬と上のすべての馬の積み重ね順を逆さまにします.

A,B,Cは移動し,移動する格子に馬がなければC,B,Aとなる.

A,D,F,G移動するセルにE,C,B,G,F,D,Aがある場合.

ブルーの場合、A番馬の移動方向が反対になり、1マス移動します.方向反転後に移動するセルが青の場合は、移動せずに静止します.

チェス盤を離脱した場合は青と同じである.

サイズ4×4人のチェス盤には馬が4頭います.

第1ラウンドは以下のように行われる.

第2ラウンドは以下のように行われる.

碁盤の大きさ,馬の位置,移動方向ともにタイミングを与え,ゲーム終了時のラウンド番号を求める.
入力
1行目は碁盤サイズN,馬の個数Kを与える.2行目からN行はチェス盤の情報を与える.チェスボードの情報は整数で構成され、各整数はセルの色を表します.0は白、1は赤、2は青です.
次のK行では、馬の情報は1番馬から順に与えられます.馬の情報は、行、列の番号、移動方向の3つの整数で構成されています.行と列の番号は1から、移動方向は4以下、1から順に→、←、↑、↓です.
同じ欄に馬が2つ以上ある場合は入力できません.
しゅつりょく
ゲーム終了時のラウンド番号を出力します.この値が1000より大きい場合、またはゲームが絶対に終了しない場合は、-1を出力します.

2.解答

2-1. 条件

白い格子で移動を続けます.

赤色の格子の場合は、裏返して移動します.

は青色のセル、または座標以外の方向を反転し、同じ場合は静止します.

2-2. に答える

実装中のシミュレーション問題.
条件が多いだけで、難点はありませんが、ちょっと面倒です.
やっぱり誰もが計画を立てて解決しよう
計画1-回路基板をスタックアレイとして宣言します.

int [] my = {0, 0, -1, 1};
int [] mx = {1, -1, 0, 0};
int [] transDir = {1, 0, 3, 2};
int[][] horses = new int[K][3]; // 말의 정보를 담을 배열
Stack<Integer>[][] stackBoard = new Stack[N][N]; // 말들을 담을 스택 보드판
Stack<Integer> white = new Stack<>(); // 흰 칸으로 이동할 때 쓰이는 임시 스택
board = new int[N][N]; // 보드판

それ以外に必要な変数も発表した.
現実世界の複雑な問題をデータ化してコンピュータが理解できるようにすることが重要である.
重要なアイデアの1つは、宣言ボードがスタックされていることです.
これは、赤いセルに移動する際に、スタックにpop万を供給すれば、問題の要求通りに実施できることを意味します.
計画2-問題の要求に従ってゲームを行う.
この部分は純実現なので特に説明はありません.
完全なコードを確認します.

3.完全なコード

import java.util.Stack;
import java.util.StringTokenizer;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N, K;
	static int[][] board;
	
	// 파랑칸 여부 (좌표 밖이거나, 2일 때)
	static boolean isBlue(int y, int x) {
		return y < 0 || y >= N || x < 0 || x >= N || board[y][x] == 2;
	}
	
	public static void main(String[] args) throws Exception {
		StringTokenizer stk = new StringTokenizer(br.readLine());
		N = Integer.parseInt(stk.nextToken());
		K = Integer.parseInt(stk.nextToken());
		
		int [] my = {0, 0, -1, 1};
		int [] mx = {1, -1, 0, 0};
		int [] transDir = {1, 0, 3, 2};
		int[][] horses = new int[K][3]; // 말의 정보를 담을 배열
		Stack<Integer>[][] stackBoard = new Stack[N][N]; // 말들을 담을 스택 보드판
		Stack<Integer> white = new Stack<>(); // 흰 칸으로 이동할 때 쓰이는 임시 스택
		board = new int[N][N]; // 보드판
		
		for (int i = 0; i < N; i++) {
			 stk = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < N; j++) {
				stackBoard[i][j] = new Stack<>();
				board[i][j] = Integer.parseInt(stk.nextToken());
			}
		}
		
		for (int i = 0; i < K; i++) {
			stk = new StringTokenizer(br.readLine());
			
			int y = Integer.parseInt(stk.nextToken()) - 1;
			int x = Integer.parseInt(stk.nextToken()) - 1;
			int dir = Integer.parseInt(stk.nextToken()) - 1;
			
			horses[i][0] = y;
			horses[i][1] = x;
			horses[i][2] = dir;
			stackBoard[y][x].add(i);
		}
		
		int ans = -1;
		int loop = 0;
		
		a: while (true) {
			loop++;
			
			// 턴 돌리기
			for (int i = 0; i < K; i++) {
				// 현재 말의 정보를 가져온다
				int[] horse = horses[i];
				int y = horse[0];
				int x = horse[1];
				int dir = horse[2];
				
				// 이동하려는 다음 칸
				int ny = y + my[dir];
				int nx = x + mx[dir];
				
				// 파랑칸일 때
				if (isBlue(ny, nx)) {
					// 좌표를 반대로 바꿔준다
					ny = y - my[dir]; 
					nx = x - mx[dir];
					horse[2] = transDir[dir];
					
					// 반대 방향도 파랑칸일 때
					if (isBlue(ny, nx)) continue;
				}
				
				switch (board[ny][nx]) {
				case 0: // 흰색
					while (!stackBoard[y][x].isEmpty()) {
						int piece = stackBoard[y][x].pop();
						white.add(piece);
						if (piece == i) break; // 현재 이동하는 말일 때 탈출
					}
					
					while (!white.isEmpty()) {
						int piece = white.pop();
						
						// 이동하는 말들의 좌표 갱신
						int[] info = horses[piece];
						info[0] = ny;
						info[1] = nx;
						
						stackBoard[ny][nx].add(piece);
					}
					break;
				case 1: // 빨간색
					while (!stackBoard[y][x].isEmpty()) {
						int piece = stackBoard[y][x].pop();
                        
                                                // 이동하는 말들의 좌표 갱신
						int[] info = horses[piece];
						info[0] = ny;
						info[1] = nx;
						
						stackBoard[ny][nx].add(piece);
                        
						if (piece == i) break; // 현재 이동하는 말일 때 탈출
					}
					break;
				}
				
				// 이동 후 말 4개 이상 모였다면 게임 끝
				if (stackBoard[ny][nx].size() >= 4) {
					ans = loop;
					break a;
				}
				
				if (loop > 1000) break a;
			}
		}
		
		bw.write(ans + "");
		bw.close();
	}
}