题目描述

Poj 1739

给你一个 $n*m$ 的地图，有的格子存在障碍，求 从左下角走到右下角 且经过所有非障碍格子一次（仅一次）的路径总数。

如图，$n = 3$ ，$m = 4$，无障碍，一共有 $4$ 种走法。

输入格式

多组数据，每组数据开头两个整数 $n$，$m$ $(0 < n,m \le 8)$，接下来描述一个 $n*m$ 的地图，“#”表示该格子有障碍，“.”表示该格子无障碍。当 $n = 0$ ，$m = 0$ 时，输入结束。

输出格式

对于每组数据，输出符合条件的路径条数。

输入输出样例

输入 #1

2 2
..
..
2 3
#..
...
3 4
....
....
....
0 0

输出 #1

1
1
4