同じ形に分割
締め切りが 2017/07/04 10:00 AM なので，その 1 分後に投稿されるように予約
設問
横 m マス、縦 n マスの長方形があります。これを同じ形の2つの領域に分割することを考えます。
ただし、それぞれの領域はすべて縦・横でつながっている（隣り合っている）ものとします。
つまり、同じ色の領域が複数に分かれてはいけませんし、斜めの場合は隣り合っているとはみなしません。
分割する位置はマスの区切りとし、斜めに分割したり、1つのマスを複数に分けたりすることはできません。
また、分割する線の位置を決めるものとし、色が逆のパターンは1つとカウントします。
なお、「同じ形」とは点対称のように回転させて重なる形とします。
例えば、m = 4, n = 3のブロックの場合、以下の左にあるような9通りの分け方があります。
右のような分け方は、つながっていないためNGです。
標準入力から m と n がスペース区切りで与えられたとき、何通りの分け方があるかを求め、
その数を標準出力に出力してください。
なお、m, n はともに正の整数で、 1 < m × n < 25 を満たすものとします。
【入出力サンプル】
標準入力
3 4
標準出力
9
============================================
R では時間制限をクリアできない
F = function(n, m) {
G = function(x) {
board = matrix(-1, n + 2, m + 2)
board[1:n + 1, 1:m + 1] = matrix(x, n, m)
ij = which(board == 1, arr.ind = TRUE)[1, ]
board[ij[1], ij[2]] = 2
repeat {
ij = which(board == 2, arr.ind = TRUE)
change = FALSE
for (k in seq_len(nrow(ij))) {
i = ij[k, 1]
j = ij[k, 2]
if (board[i - 1, j] == 1) {
change = TRUE
board[i - 1, j] = 2
}
if (board[i + 1, j] == 1) {
change = TRUE
board[i + 1, j] = 2
}
if (board[i, j - 1] == 1) {
change = TRUE
board[i, j - 1] = 2
}
if (board[i, j + 1] == 1) {
change = TRUE
board[i, j + 1] = 2
}
}
if (change == FALSE) {
break
}
}
return(all(board != 1))
}
H = function(x) {
x = matrix(x, n, m)
return(all(x + x[n:1, m:1] == 1))
}
bincombinations = function(p) {
retval = matrix(0, nrow = 2^p, ncol = p)
for (n in 1:p) {
retval[, n] = rep(rep(0:1, each = 2^(p - n)), length = 2^p)
}
retval
}
mn = m * n
if (mn%%2 == 1) {
return(0)
}
mn2 = mn/2
a = cbind(0, bincombinations(mn - 1)) # 半分だけ調べればよい
b = rowSums(a) == mn2 # 同じ色のセル数が等しいか
c = a[b, ]
d = apply(c, 1, H) # 同じ形か
e = c[d, ]
f = apply(e, 1, G) # 縦横でつながっているか
g = e[f, ]
cat(nrow(g))
}
system.time(F(4, 4)) # 22, 0.211 sec.
system.time(F(3, 4)) # 9, 0.137 sec.
system.time(F(2, 8)) # 8, 0.055 sec.
system.time(F(4, 5)) # 39, 1.177 sec.
F(3, 7) # 0
system.time(F(4, 6)) # 90, 12.406 sec.
===========================================
Java 7 は遅いが，Java 8 で OK
import java.util.Scanner;
public class SameShape {
public static void main(String[] args) {
if (false) {
long start = System.currentTimeMillis();
System.out.println(F(4, 4)); // 22
System.out.println(F(3, 4)); // 9
System.out.println(F(2, 8)); // 8
System.out.println(F(4, 5)); // 39
System.out.println(F(3, 7)); // 0
System.out.println(F(4, 6)); // 90
long end = System.currentTimeMillis();
System.out.println((end - start) + "ms");
} else {
Scanner cin = new Scanner(System.in);
String line;
line = cin.nextLine();
String [] line2 = line.split(" ");
int n = Integer.parseInt(line2[0]);
int m = Integer.parseInt(line2[1]);
System.out.println(F(n, m));
}
}
static int F(int n, int m) {
int mn = m * n;
if ((int) mn % 2 == 1) {
return 0;
}
int mn2 = mn / 2;
int i, j, p;
int[] y = new int[mn];
int color;
int count = 0;
for (i = (int) Math.pow(2, mn2) - 1; i < Math.pow(2, mn - 1); i += 2) {
p = i;
color = 0;
for (j = 0; j < mn; j++) {
y[j] = p & 0x00000001;
if (y[j] == 1) {
++color;
}
p >>= 1;
}
if (color == mn2 && G(y, n, m)) {
count++;
}
}
return count;
}
static boolean G(int[] x, int n, int m) {
int[][] board = new int[n + 2][m + 2];
int i, j, k = 0;
int xLength = x.length;
for (i = 0; i < xLength / 2; i++) {
if (x[i] + x[xLength - 1 - i] != 1)
return false;
}
for (i = 1; n >= i; i++) {
for (j = 1; m >= j; j++) {
board[i][j] = x[k++];
}
}
for (i = 1; n >= i; i++) {
for (j = 1; m >= j; j++) {
if (board[i][j] + board[n + 1 - i][m + 1 - j] != 1)
return false;
}
}
boolean flag = false;
for (i = 1; n >= i; i++) {
for (j = 1; m >= j; j++) {
if (board[i][j] == 1) {
board[i][j] = 2;
flag = true;
break;
}
}
if (flag) {
break;
}
}
for (;;) {
int count = 0;
boolean change = false;
int[] ii = new int[24];
int[] jj = new int[24];
for (i = 1; n >= i; i++) {
for (j = 1; m >= j; j++) {
if (board[i][j] == 2) {
ii[count] = i;
jj[count] = j;
count++;
}
}
}
for (k = 0; k < count; k++) {
i = ii[k];
j = jj[k];
if (board[i - 1][j] == 1) {
change = true;
board[i - 1][j] = 2;
}
if (board[i + 1][j] == 1) {
change = true;
board[i + 1][j] = 2;
}
if (board[i][j - 1] == 1) {
change = true;
board[i][j - 1] = 2;
}
if (board[i][j + 1] == 1) {
change = true;
board[i][j + 1] = 2;
}
}
if (change == false) {
break;
}
}
for (i = 1; n >= i; i++) {
for (j = 1; m >= j; j++) {
if (board[i][j] == 1) {
return false;
}
}
}
return true;
}
}
