AOJ 1321 - Captain Q's Treasure

AOJ

ICPCアジア地区予選に向けて

問題

h×wのマップが与えられる
セルの意味は以下

  • 数字セル：９近傍に宝がその数字の数だけ埋まっている
  • '*'：宝が埋まっているかもしれない
  • '.'：何も埋まってない

このとき埋まっている宝の数は最小でいくらか

制約

1<=h,w<=15
1<=数字セルの数<=15

解法

数字セルの９隣接を順に宝が埋まっているとするかしないかを決めていく。
i番目の数字セルの値をnum[i]とする。
あるセルに宝が埋まっていることにしたら、その９隣接にある数字セルのnum[i]を１小さくする
状態は

  • どこまでセルを見たか（最大15*9）
  • num[i]（最大10^15）

終了条件は

  • num[i]が全て0

高速化

  • num[i]はlong longにエンコードする。
  • mapでメモ化
  • 今後見るセル全て宝が埋まっていることにしても、num[i]が0にならないものがあれば枝刈り
  • 探索順を工夫