数字が最大のマインスイーパ
締め切りが 2017/7/11 10:00 AM なので，その 1 分後に投稿されるように予約
Windows のゲームとして有名なマインスイーパ。
長方形のマスの中に地雷が埋まっており、その隣接するマスに書かれている数字を元に、地雷の場所を特定します。
このとき、隣接するというのは、上下左右だけでなく、斜めの位置も含みます。
なお、地雷があるマスに数字が書かれることはありません。
m × n のマスの中に a 個の地雷が配置されている場合を考えます。
このとき、このマスの中に書かれている数字の和の最大値を求めます。
例えば、m = 4, n = 4, a = 3 のとき、以下の「＊」の位置に地雷を配置すると、数字の和の最大値は19となります。
標準入力から m, n, a がスペース区切りで与えられたとき、その数字の和の最大値を求め、標準出力に出力してください。
なお、m, n, a はいずれも正の整数で、m × n ≦ 28、 a ≦ 4 を満たすものとします。
【入出力サンプル】
標準入力
4 4 3
標準出力
19
================================================
R では時間制限に引っかかる。
f = function(m, n, a) {
g = function(y) {
z = matrix(0, m, n)
z[y] = 1
w = matrix(0, m + 2, n + 2)
w[1:m + 1, 1:n + 1] = z
s = 0
for (i in 1:m + 1) {
for (j in 1:n + 1) {
if (w[i, j] == 0) {
s = s +sum(w[i+(-1:1), j+(-1:1)])
}
}
}
s
}
mn = m * n
s = combn(mn, a, g)
cat(max(s))
}
system.time(f(3, 3, 2)) # 11, 0.035 sec.
system.time(f(4, 4, 3)) # 19, 0.017 sec.
system.time(f(5, 5, 4)) # 32, 0.540 sec.
system.time(f(4, 7, 4)) # 30, 1.004 sec.
system.time(f(3, 9, 4)) # 32, 0.872 sec.
Java で書いて OK
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
if (false) {
System.out.println(f(3, 3, 2));
System.out.println(f(4, 4, 3));
System.out.println(f(5, 5, 4));
System.out.println(f(4, 7, 4));
System.out.println(f(3, 9, 4));
} else {
int m, n, a;
Scanner cin = new Scanner(System.in);
String line;
line = cin.nextLine();
String[] line2 = line.split(" ");
m = Integer.parseInt(line2[0]);
n = Integer.parseInt(line2[1]);
a = Integer.parseInt(line2[2]);
System.out.println(f(m, n, a));
}
}
static int f(int m, int n, int a) {
int[][] z = new int[m + 2][n + 2];
int i, j;
int[] y = new int[a + 1];
int[] x = new int[m * n + 1];
for (i = 1; m * n >= i; i++) {
x[i] = i;
}
int[][] ind = combn(x, m * n, a);
int s = 0;
for (j = 1; j < ind[0].length; j++) {
for (i = 1; a >= i; i++) {
y[i] = ind[i][j] - 1;
}
s = Math.max(s, g(y, m, n));
}
return s;
}
static int g(int[] y, int m, int n) {
int i, j, ix, iy;
int[][] w = new int[m + 2][n + 2];
for (i = 1; i < y.length; i++) {
ix = (y[i] % m) + 1;
iy = (int) (y[i] / m) + 1;
w[ix][iy] = 1;
}
int s = 0;
for (i = 1; i < m + 1; i++) {
for (j = 1; j < n + 1; j++) {
if (w[i][j] == 0) {
s = s + w[i - 1][j - 1] + w[i][j - 1] + w[i + 1][j - 1]
+ w[i - 1][j] + w[i + 1][j] + w[i - 1][j + 1]
+ w[i][j + 1] + w[i + 1][j + 1];
}
}
}
return s;
}
static double factorial(int n) {
int i;
double result = 1;
for (i = 1; n >= i; i++) {
result *= i;
}
return result;
}
static int[][] combn(int[] x, int n, int m) {
int e, h, i, j, nmmp1, lenr;
int[] a = new int[m + 1];
int[] r = new int[m + 1];
int count = (int) (factorial(n) / factorial(m) / factorial(n - m));
int[][] out = new int[m + 1][count + 1];
e = 0;
h = m;
for (i = 1; m >= i; i++) {
a[i] = i;
r[i] = x[i];
}
lenr = r.length - 1;
for (j = 1; count >= j; j++) {
for (i = 1; lenr >= i; i++) {
out[i][j] = r[i];
}
}
i = 2;
nmmp1 = n - m + 1;
while (a[1] != nmmp1) {
if (e < n - h) {
h = 1;
e = a[m];
} else {
e = a[m - h];
h++;
}
for (j = 1; h >= j; j++) {
a[m - h + j] = e + j;
}
for (j = 1; m >= j; j++) {
out[j][i] = x[a[j]];
}
i++;
}
return out;
}
}
