結果

問題 No.228 ゆきこちゃんの 15 パズル
コンテスト
ユーザー jp_ste
提出日時 2016-02-19 20:12:32
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

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