CodeIQ:数字が最大のマインスイーパ

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「数字が最大のマインスイーパ」(CodeIQ)を参照してください。

問題の概要

問題を引用します。
Windows のゲームとして有名なマインスイーパ。
長方形のマスの中に地雷が埋まっており、その隣接するマスに書かれている数字を元に、地雷の場所を特定します。
このとき、隣接するというのは、上下左右だけでなく、斜めの位置も含みます。
なお、地雷があるマスに数字が書かれることはありません。

m × n のマスの中に a 個の地雷が配置されている場合を考えます。
このとき、このマスの中に書かれている数字の和の最大値を求めます。

例えば、m = 4, n = 4, a = 3 のとき、以下の「*」の位置に地雷を配置すると、数字の和の最大値は19となります。

 111
13*2
*3*2
1211

標準入力から 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

解説

あまりうまい方法を思いつきませんでした。

考え方

うまい方法を思いつかなかったので総当たりです。
最大で爆弾の配置は28C4=20475通りしかないので総当たりでもいけます。

私は計算を単純にするため、次の様にしました。
まずm*nの二次元配列を作り、全ての値を0で初期化しておきます。
次に左上のマスを0、右下のマスを(m*n-1)とし、0〜(m*n-1)の番号からa個を選んだ組み合わせ列挙します。
これが爆弾の位置になるのでその周囲のマス全てを+1します。
最後に爆弾の位置の値を0で上書きし、全体の数を合計すると答えになります。

main

入力値を数値にしてsolve()に渡し、結果を印字します。

solve(m,n,a)

引数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行目で最大値を更新します。

最終的に最大値を返却します。

雑感

もっとうまい方法があるんだろうなあぁと思います。
どうでも良いことですが、この問題は新幹線に乗っている時、どうせ暇なんだからやれば良いじゃないかと思いついて岡山から広島の間にやりました。