Captain Q's Treasure (AOJ 1321)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1321

問題

マインスイーパーの盤面を与えるので爆弾を置く数を最小化しろ。
1<=h,w<=15
ヒントの数<=15
爆弾を置けるのは*かヒントの位置

解法

各数値の周り9マスを順番に見る＋どこまで見たかと数値の周りにあと何個爆弾を置けるかでメモ化探索。