私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「数字が最大のマインスイーパ」（CodeIQ）を参照してください。
Windows のゲームとして有名なマインスイーパ。
長方形のマスの中に地雷が埋まっており、その隣接するマスに書かれている数字を元に、地雷の場所を特定します。
このとき、隣接するというのは、上下左右だけでなく、斜めの位置も含みます。
なお、地雷があるマスに数字が書かれることはありません。
m × n のマスの中に a 個の地雷が配置されている場合を考えます。
このとき、このマスの中に書かれている数字の和の最大値を求めます。
例えば、m = 4, n = 4, a = 3 のとき、以下の「＊」の位置に地雷を配置すると、数字の和の最大値は19となります。
1 1 1 1 3 * 2 * 3 * 2 1 2 1 1
標準入力から m, n, a がスペース区切りで与えられたとき、その数字の和の最大値を求め、標準出力に出力してください。
なお、m, n, a はいずれも正の整数で、m × n ≦ 28、 a ≦ 4 を満たすものとします。
【入出力サンプル】
標準入力
4 4 3
標準出力
19
Rubyで解答しています。
#!/usr/bin/ruby
def solve(m,n,a)
mx = -1
dirs = [[-1,-1], [-1,0], [-1,+1], [0, -1], [0, +1], [+1, -1], [+1, 0], [+1, +1]]
(0...(m*n)).to_a.combination(a){|arr|
map = Array.new(m){Array.new(n,0)}
for bom in arr
y = bom / n
x = bom % n
for d in dirs
ay = y + d[0]
ax = x + d[1]
next if (ax < 0) || (ay < 0) || (n <= ax) || (m <= ay)
map[ay][ax] += 1
end
end
for bom in arr
y = bom / n
x = bom % n
map[y][x] = 0
end
v = map.flatten.reduce(:+)
mx = v if v > mx
}
return mx
end
# main
while line = gets
line.strip!
next if line.empty?
m, n, a = line.split.map{|v| v.to_i}
p solve(m,n,a)
end
あまりうまい方法を思いつきませんでした。
入力値を数値にしてsolve()に渡し、結果を印字します。
引数m,n,aは入力値です。
mxはマスの数字の合計値の最大値を保持する領域で、最終的に答えになります。
dirは隣接位置を示す値です。
7行目で1〜(m*n-1)からa個の数を選んだ時の組み合わせを順次取得し、その全てに対してマスの数の合計を求めます。
8行目の2次元配列は隣接する爆弾数を記録するためのマップです。
10〜21行目で全ての爆弾の位置に対し、その周囲の数字を決定しています。
11〜12行目で1〜(m*n-1)の番号を2次元配列の座標に変換します。
14〜19行目で爆弾のあるマスの周囲のマスの値を1増やします。
18行目は範囲外のチェックです。
23〜28行目で爆弾のあるマスの値を0で上書きしています。
30行目で全てのマスの値を合計し、それが現在のmxより大きければ31行目で最大値を更新します。
最終的に最大値を返却します。
もっとうまい方法があるんだろうなあぁと思います。
どうでも良いことですが、この問題は新幹線に乗っている時、どうせ暇なんだからやれば良いじゃないかと思いついて岡山から広島の間にやりました。