[yukicoder] No.228 ゆきこちゃんの 15 パズル

問題

No.228 ゆきこちゃんの 15 パズル - yukicoder

15パズルに関する問題です。問題の制約のおかげで、レベル2となっているんだと思います。普通にパズルが解けるかどうかという問題になると、レベルが上がると思います。

考え方

一度動かした駒はもう一度動かすことができないという制約がこの問題の肝だと思います。

この制約から、最初の盤面の 以外の駒に対して正規の位置 (パズルが解けたときの盤面) との距離を計算します。

この距離が 以上の駒があるとその盤面は解くことができません。

この条件だけでは足りないので、実際に全ての駒の距離が 以下の　盤面に対してその盤面が解けるかどうかを調べます。

空きマスは となっていますが、話の都合上、 の駒と呼ぶことにします。

の駒の移動回数は、距離が となっている駒の数になります。これは、正規の位置にいる駒を動かしてしまうと、パズルを解くことができないためです。

ここで、 の駒の位置が 行 列にいるとします。この位置から上下左右の四方向にたいして、探索していきます。

に存在するべき駒は、

です。これは数値と位置の関係は一対一に対応していることを利用しています。また、行と列は から数えています。

四方向のマスに の駒があればその駒を動かして、 の駒の位置も動かします。この操作を距離が となっている駒の数の回数行うことができれば、パズルが解くことができます。

コード

import java.util.Scanner;

public class Exec0228 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int[][]p = new int[4][4];
        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 4; j++) {
                p[i][j] = scan.nextInt();
            }
        }
        scan.close();
        int r0 = 0;
        int c0 = 0;
        int cnt = 0;
        for(int i = 0; i < 4; i++) {
            for(int j = 0; j < 4; j++) {
                int t = p[i][j];
                if(t == 0) {
                    r0 = i;
                    c0 = j;
                    continue;
                }
                int l = len(t, i, j);
                if(l >= 2) {
                    System.out.println("No");
                    System.exit(0);
                }else if(l == 1) {
                    cnt ++;
                }
            }
        }
        int []dx = {1, -1, 0, 0};
        int []dy = {0, 0, 1, -1};
        boolean flag = true;
        for(int i = 0; i < cnt; i++) {
            flag = true;
            for(int j = 0; j < 4; j++) {
                int nr = dx[j] + r0;
                int nc = dy[j] + c0;
                if(nr < 0 || nc < 0 || nr > 3 || nc > 3) {
                    continue;
                }
                int k = p[nr][nc];
                int n = num(r0, c0);
                if(n == k) {
                    p[r0][c0] = k;
                    r0 = nr;
                    c0 = nc;
                    flag = false;
                    break;
                }
            }
            if(flag) {
                System.out.println("No");
                System.exit(0);
            }
        }
        System.out.println("Yes");
    }
    static int len(int n, int nr, int nc) {
        int r = n / 4;
        int c = n % 4;
        if(c == 0) {
            c = 3;
            r -= 1;
        }else {
            c -= 1;
        }
        int l = Math.abs(nr - r) + Math.abs(nc - c);
        return l;
    }
    static int num(int r, int c) {
        int n = 0;
        n = r * 4 + c + 1;
        return n;
    }
}