上下左右に箱を並べよう

上下左右に箱を並べよう

締め切りが 2017/07/25 10:00 AM なので，その 1 分後に投稿されるように予約

設問

大手衣料品店のスマートフォンアプリとコラボレーションして話題になっている、ゲーム機での人気ゲームがあります。
(例えばこのようなゲームがイメージです→) http://www.uniqlo.com/jp/hacoboy/　※CodeIQ外のサイトに飛びます。
このゲームのように、箱を並べるパターンが何通りあるかを求めることを考えます。

ここでは図のような格子状のマスにおいて、ある位置からスタートして、上下左右の隣り合う位置に箱を配置していきます。
すでに箱が配置されている位置、開始位置には箱を配置できません。
なお、上記のゲームでは最初に下方向に配置することはできませんが、本問では最初から下方向も可能とします。

配置する箱の数 n が与えられたとき、その箱の配置方法が何通りあるかを求めます。
ただし、できあがった位置と形だけで判断するものとし、その手順が異なっても同じ位置・同じ形であれば同じものとします。
例えば n = 3 のとき、以下のパターンはいずれも同じものとします。

n = 3 のとき、その箱の配置方法は以下の図のように上方向からスタートするものが9通り、そのほか全部で32通りがあります。

標準入力から n が与えられたとき、その箱の配置方法が何通りあるかを求め、標準出力に出力してください。
なお、n は 9以下の正の整数とします。

【入出力サンプル】
標準入力
3

標準出力
32

==========================================

R

quatrcombinations = function(p) {
    retval = matrix(" ", nrow = 4^p, ncol = p)
    for (n in 1:p) {
        retval[, n] = rep(c(rep("U", 4^(p-n)), rep("D", 4^(p-n)), rep("L", 4^(p-n)),
            rep("R", 4^(p-n))), length = 4^p)
    }
    retval
}

f = function(n) {
    a = quatrcombinations(n)
    size =  2*(n+1)-n%%2
    result = NULL
    apply(a, 1, function(p) {
        board = matrix(0, size, size)
        x = y = n+1
        board[x, y] = 1
        ok = TRUE
        for (path in p) {
            if (path == "U") {
                y = y-1
            } else if (path == "D") {
                y = y+1
            } else if (path == "L") {
                x = x-1
            } else {
                x = x+1
            }
            if (board[x, y] == 1) {
                ok = FALSE
                break
            }
            board[x, y] = 1
        }
        if (ok == TRUE) {
            rbind(result , c(board)) ->> result
        }
    })
    cat(nrow(unique(result)))
}
system.time(f(6))
# f(1) # 4
# f(2) # 12
# f(3) # 32
# f(4) # 92
# f(5) # 248
# f(6) # 696
# f(7) # 1872
# f(8) # 5169

================================================

Java 8

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        int i, j, k, l, n, size, w, zz;
if (true) {
    n = 9; // 13876
} else {
    Scanner cin = new Scanner(System.in);
    String line;
    line = cin.nextLine();
    n = Integer.parseInt(line);
}
        size = 2 * (n + 1) - n % 2;
        int mx = (int) Math.pow(4, n);
        int[][] result = new int[mx][n + 1];
        int count = 0;
        for (i = 0; i < mx; i++) {
            zz = i;
            int[][] board = new int[size][size];
            int x, y;
            x = y = n;
            board[x][y] = 1;
            boolean ok = true;
            for (j = 0; j < n; j++) {
                w = (int) (zz % 4);
                zz = zz / 4;
                if (w == 0) {
                    x++;
                } else if (w == 1) {
                    x--;
                } else if (w == 2) {
                    y++;
                } else {
                    y--;
                }
                if (board[x][y] == 1) {
                    ok = false;
                    break;
                }
                board[x][y] = 1;
            }
            if (ok) {
                int cnt = 0;
                for (k = 0; k < size; k++) {
                    for (l = 0; l < size; l++) {
                        if (board[k][l] == 1) {
                            result[count][cnt++] = k * 10 + l;
                        }
                    }
                }
                count++;
            }
        }
        int count2 = 0;
        for (i = 0; i < count; i++) {
            if (result[i][0] == -1) {
                continue;
            }
            for (j = i + 1; j < count - 1; j++) {
                boolean equal = true;
                for (k = 0; n >= k; k++) {
                    if (result[i][k] != result[j][k]) {
                        equal = false;
                        break;
                    }
                }
                if (equal) {
                    result[j][0] = -1;
                }
            }
        }
        for (i = 0; i < count; i++) {
            if (result[i][0] != -1) {
                count2++;
            }
        }

        System.out.println("count2 = " + count2);
        long end = System.currentTimeMillis();
        System.out.println((end - start) + "ms");
    }

}