結果

問題 No.228 ゆきこちゃんの 15 パズル
ユーザー jp_stejp_ste
提出日時 2016-02-19 20:12:32
言語 Java21
(openjdk 21)
結果
AC  
実行時間 159 ms / 5,000 ms
コード長 1,621 bytes
コンパイル時間 2,496 ms
コンパイル使用メモリ 77,500 KB
実行使用メモリ 54,896 KB
最終ジャッジ日時 2024-09-22 12:21:29
合計ジャッジ時間 6,151 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 154 ms
54,896 KB
testcase_01 AC 128 ms
54,188 KB
testcase_02 AC 134 ms
54,004 KB
testcase_03 AC 159 ms
54,664 KB
testcase_04 AC 131 ms
54,508 KB
testcase_05 AC 132 ms
54,260 KB
testcase_06 AC 134 ms
54,300 KB
testcase_07 AC 158 ms
54,820 KB
testcase_08 AC 135 ms
54,028 KB
testcase_09 AC 136 ms
54,060 KB
testcase_10 AC 121 ms
54,056 KB
testcase_11 AC 157 ms
54,548 KB
testcase_12 AC 158 ms
54,524 KB
testcase_13 AC 158 ms
54,568 KB
testcase_14 AC 155 ms
54,624 KB
testcase_15 AC 156 ms
54,416 KB
testcase_16 AC 157 ms
54,620 KB
testcase_17 AC 155 ms
54,720 KB
testcase_18 AC 157 ms
54,604 KB
testcase_19 AC 153 ms
54,700 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