8256: BZOJ4256：推箱子

经典的推箱子是一个来自日本的古老游戏，目的是在训练你的逻辑思考能力。在一个狭 小的仓库中，要求把木箱放到指定的位置，稍不小心就会出现箱子无法移动或者通道被堵住 的情况，所以需要巧妙的利用有限的空间和通道，合理安排移动的次序和位置，才能顺利的 完成任务。 这个游戏有一个相对简单的版本， 就是只有一个木箱， 要将其推到一个确定的目标位置。 举个例子： ..#@. .X.O. ##..# 其中“.”表示没有障碍的格子，“#”表示有障碍的格子，“X”表示目标位置（注意这个格 子是没有障碍的） ，“O”是箱子（对于人来说箱子存在的格子是不能越过的） ，“@”是人的位 置。注意上面这个情况是可以将箱子推到目标点去的，因为人只要向右一格，向下一格，然 后推着箱子向左走两格，就完成了任务。 而下面这个例子是无解的： ..#.. .X.O. ##.@# 现在我们的主人公想知道，对于一个给定的地图（与上面两个不同的是没有了箱子和人 的初始位置） ，有多少种箱子和人的初始摆放方法（箱子的初始位置和人的初始位置和目标 位置必须两两不同）能够使得箱子能被人成功地推到目标位置。

输入格式

第一行为两个正整数 n,m。表示整个地图有 n行 m 列。N,M均小于等于1000 接下来是一个 n行 m 列的地图，用 n个长为 m 的字符串表示。

输出格式

一行，包含一个整数，为方案总数。

样例输入

3 5
..#..
.X...
##..#

样例输出

9

提示

没有写明提示

题目来源

JOI2012