結果
| 問題 | No.228 ゆきこちゃんの 15 パズル |
| ユーザー |
 suigingin
|
| 提出日時 | 2015-06-19 22:53:23 |
| 言語 | Java (openjdk 23) |
| 結果 |
AC
|
| 実行時間 | 110 ms / 5,000 ms |
| コード長 | 4,128 bytes |
| コンパイル時間 | 3,193 ms |
| コンパイル使用メモリ | 79,408 KB |
| 実行使用メモリ | 54,220 KB |
| 最終ジャッジ日時 | 2024-07-07 04:10:10 |
| 合計ジャッジ時間 | 6,325 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 17 |
ソースコード
import java.util.Arrays;import java.util.Scanner;public class M2 {MyScanner sc = new MyScanner();Scanner sc2 = new Scanner(System.in);long start = System.currentTimeMillis();long fin = System.currentTimeMillis();final int MOD = 1000000007;int[] dx = { 1, 0, 0, -1 };int[] dy = { 0, 1, -1, 0 };int[][] n;boolean[] used;boolean ok;void run() {n = sc.nextInt2dArray(4, 4);used = new boolean[16];ok = false;int sh = 0;int sw = 0;for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {if (n[i][j] == -1) {sh = i;sw = j;break;}}}dfs(n, sh, sw);System.out.println(ok ? "Yes" : "No");}void dfs(int[][] order, int h, int w) {if(ok) return;if (judge(order)) {ok = true;return;}for (int i = 0; i < 4; i++) {int nexth = h + dy[i];int nextw = w + dx[i];if (inner(nexth, nextw, 4, 4)) {int number = order[nexth][nextw];if (!used[number]) {used[number] = true;order[nexth][nextw] = order[h][w];order[h][w] = number;dfs(order, nexth, nextw);used[number] = false;order[h][w] = -1;order[nexth][nextw] = number;}}}}boolean judge(int[][] order) {int n = 0;for (int i = 0; i < 4; i++) {for (int j = 0; j < 4; j++) {if (i == 3 && j == 3)break;if (order[i][j] != n++)return false;}}return order[3][3] == -1 ? true : false;}void dfs(int[] order) {}public static void main(String[] args) {new M2().run();}void debug(Object... o) {System.out.println(Arrays.deepToString(o));}void debug2(char[][] array) {for (int i = 0; i < array.length; i++) {for (int j = 0; j < array[i].length; j++) {System.out.print(array[i][j]);}System.out.println();}}boolean inner(int h, int w, int limH, int limW) {return 0 <= h && h < limH && 0 <= w && w < limW;}void swap(int[] x, int a, int b) {int tmp = x[a];x[a] = x[b];x[b] = tmp;}// find minimum i (a[i] >= border)int lower_bound(int a[], int border) {int l = -1;int r = a.length;while (r - l > 1) {int mid = (l + r) / 2;if (border <= a[mid]) {r = mid;} else {l = mid;}}// r = l + 1return r;}boolean palindrome(String s) {for (int i = 0; i < s.length() / 2; i++) {if (s.charAt(i) != s.charAt(s.length() - 1 - i)) {return false;}}return true;}class MyScanner {int nextInt() {try {int c = System.in.read();while (c != '-' && (c < '0' || '9' < c))c = System.in.read();if (c == '-')return -nextInt();int res = 0;do {res *= 10;res += c - '0';c = System.in.read();} while ('0' <= c && c <= '9');return res;} catch (Exception e) {return -1;}}double nextDouble() {return Double.parseDouble(next());}long nextLong() {return Long.parseLong(next());}String next() {try {StringBuilder res = new StringBuilder("");int c = System.in.read();while (Character.isWhitespace(c))c = System.in.read();do {res.append((char) c);} while (!Character.isWhitespace(c = System.in.read()));return res.toString();} catch (Exception e) {return null;}}int[] nextIntArray(int n) {int[] in = new int[n];for (int i = 0; i < n; i++) {in[i] = nextInt() - 1;}return in;}int[][] nextInt2dArray(int n, int m) {int[][] in = new int[n][m];for (int i = 0; i < n; i++) {in[i] = nextIntArray(m);}return in;}double[] nextDoubleArray(int n) {double[] in = new double[n];for (int i = 0; i < n; i++) {in[i] = nextDouble();}return in;}long[] nextLongArray(int n) {long[] in = new long[n];for (int i = 0; i < n; i++) {in[i] = nextLong();}return in;}char[][] nextCharField(int n, int m) {char[][] in = new char[n][m];for (int i = 0; i < n; i++) {String s = sc.next();for (int j = 0; j < m; j++) {in[i][j] = s.charAt(j);}}return in;}}}