Sokoban(倉庫番) - joi2012-day3

時間制限: 2秒

メモリ制限: 512MB

「倉庫番」は，長年人々に愛され続けてきているパズルである．

「倉庫番」は 縦M \times 横N マスの正方形に区切られた盤面で行われる．盤面上に箱があり，プレイヤーを操作して箱を目標地点へ動かすことが目的である．この問題では，箱が 1 個である場合を考える．盤面の一部のマスは壁であり，プレイヤー・箱・目標地点は壁でない 1 マスに位置している(プレイヤーや箱は盤面から出ることはない)．以下のいずれかの操作が可能である．

プレイヤーがいるマスに隣接しているマスのうち壁でなく箱がないマスを 1 つ選び，プレイヤーをそのマスへ移動させる．
プレイヤーがいるマスと箱があるマスが隣接していて，さらに，箱のマスに隣接していてプレイヤーと反対側にある壁でないマスが存在するとき，箱をそのマスに動かし，プレイヤーを箱があったマスに移動させる．

ここで，マスとマスが隣接しているとは，それらのマスが 1 辺を共有することである．

以下に，「倉庫番」の問題の例を示す．文字 # は壁，文字 @ はプレイヤー，文字 O は箱，文字 X は目標地点，文字 . はその他のマス目を表している．

..#@.
.X.O.
##..#

この状態からは，以下の操作によって箱を目標地点へ動かすことができる．

プレイヤーを右に動かす．
プレイヤーを下に動かす．
箱とプレイヤーを左に動かす．
箱とプレイヤーを左に動かす．

一方，次の状態からは箱を目標地点へ動かすことはできない．

..#..
.X.O.
##.@#

あなたは，盤面の壁の位置と目標地点が決まっているとき，プレイヤーと箱を配置して，解ける「倉庫番」の問題が何通りできるか知りたい．ここで，解ける「倉庫番」の問題とは，操作を何回か繰り返して箱を目標地点へ移動させることができるような初期配置を指す．また， プレイヤーと箱はそれぞれ壁でなく目標地点と異なるマスに配置しなければならず，プレイヤーと箱は異なるマスに配置しなければならない ．

課題

盤面の大きさおよび盤面の壁の位置と目標地点が与えられたとき，
解ける「倉庫番」の問題が何通りできるかを求めるプログラムを作成せよ．

制限

`1 \leqq M \leqq 1\,000`	盤面の縦の長さ
`1 \leqq N \leqq 1\,000`	盤面の横の長さ

入力

標準入力から以下の入力を読み込め．

1 行目には整数 M, N が空白を区切りとして書かれており，それぞれ盤面の縦と横の長さを表す．
続く M 行は盤面の情報を表す．各行は N 文字からなる．各文字は # X . のいずれかであり，文字 # は壁，文字 X は目標地点，文字 . はその他のマス目 (プレイヤーや箱の初期位置の候補でもある) を表している．文字 X はちょうど 1 回現れる．

出力

標準出力に，解ける「倉庫番」の問題が何通りできるかを表す整数を 1 行で出力せよ．

採点基準

採点用データのうち，配点の 20% 分については，M \leqq 50, N \leqq 50 を満たす．

入出力例

入力例1	出力例1
`3 5 ..#.. .X... ##..#`	`9`

解ける「倉庫番」の問題は以下に示す 9 通りが考えられる．

..#@.    ..#.@    ..#..    ..#..    ..#..    ..#..    ..#@.    ..#.@    ..#..
.XO..    .XO..    .XO@.    .XO.@    .XO..    .XO..    .X.O.    .X.O.    .X.O@
##..#    ##..#    ##..#    ##..#    ##@.#    ##.@#    ##..#    ##..#    ##..#

入力例2	出力例2
`2 3 .X. ...`	`0`

この例では，解ける「倉庫番」の問題を作ることができない．

入力例3	出力例3
`4 7 .#.#.## ##.#..# ....X.. ##.#...`	`24`