結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー jp_stejp_ste
提出日時 2016-02-19 20:12:32
言語 Java21
(openjdk 21)
結果
AC  
実行時間 180 ms / 5,000 ms
コード長 1,621 bytes
コンパイル時間 2,434 ms
コンパイル使用メモリ 77,228 KB
実行使用メモリ 59,424 KB
最終ジャッジ日時 2023-10-23 18:33:20
合計ジャッジ時間 6,615 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 171 ms
58,204 KB
testcase_01 AC 139 ms
57,576 KB
testcase_02 AC 146 ms
57,468 KB
testcase_03 AC 173 ms
58,436 KB
testcase_04 AC 143 ms
57,244 KB
testcase_05 AC 140 ms
57,160 KB
testcase_06 AC 145 ms
57,220 KB
testcase_07 AC 170 ms
58,268 KB
testcase_08 AC 142 ms
57,732 KB
testcase_09 AC 146 ms
57,468 KB
testcase_10 AC 148 ms
57,608 KB
testcase_11 AC 177 ms
58,376 KB
testcase_12 AC 175 ms
58,096 KB
testcase_13 AC 178 ms
58,256 KB
testcase_14 AC 171 ms
58,380 KB
testcase_15 AC 176 ms
59,424 KB
testcase_16 AC 180 ms
58,152 KB
testcase_17 AC 176 ms
58,240 KB
testcase_18 AC 178 ms
58,616 KB
testcase_19 AC 176 ms
56,208 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.util.Scanner;

public class Main {
	
	static int dx[] = { 1, 0, 0, -1 };
	static int dy[] = { 0, 1, -1, 0 };
	
	public static void main(String[] args) {
		try (Scanner scan = new Scanner(System.in)) {
			int list[][] = new int[4][4];
			boolean flag[][] = new boolean[4][4];
			int zx = 0, zy = 0;
			for(int i=0; i<4; i++) {
				for(int j=0; j<4; j++) {
					list[i][j] = scan.nextInt();
					if(list[i][j] == 0) {
						zx = j;
						zy = i;
					}
				}
			}
			boolean find = solve(list, flag, zx, zy);
			
			if(find) {
				System.out.println("Yes");
			} else {
				System.out.println("No");
			}
		}
	}
	static boolean check(int[][] list) {
		for(int i=0; i<4; i++) {
			for(int j=0; j<4; j++) {
				int value = i*4 + j + 1;
				if(i==3 && j==3) value = 0;
				if(list[i][j] != value) { 
					return false;
				}
			}
		}
		return true;
	}
		
	static boolean solve(int [][] list, boolean flag[][], int zx, int zy) {
		if(check(list)) return true;
		
		boolean find = false;
		
		for(int i=0; i<4; i++) {
			int nextX = zx + dx[i];
			int nextY = zy + dy[i];
			
			if(nextX >= 0 && nextX <= 3 && nextY >= 0 && nextY <= 3 && !flag[nextY][nextX]) {
				int[][] nextList = new int[4][4];;
				for(int j=0; j<4; j++) {
					nextList[j] = list[j].clone();
				}
				nextList[zy][zx] = list[nextY][nextX];
				nextList[nextY][nextX] = 0;
				
				boolean[][] nextFlag = new boolean[4][4];
				for(int j=0; j<4; j++) {
					nextFlag[j] = flag[j].clone();
				}
				nextFlag[zy][zx] = true;
				
				find = solve(nextList, nextFlag, nextX, nextY);
				if(find) {
					break;
				}
			}
		}
		return find;
	}
}
0