1358 : 迷宫问题

时间限制:1 Sec 内存限制:128 MiB
提交:161 答案正确:98

提交 状态 讨论区

题目描述

ACM是一个喜欢玩游戏的小孩,他喜欢玩智力游戏,比如最近在玩走迷宫,这是一款超级耗费脑细胞的游戏

和普通的走迷宫一样,游戏是一张迷宫图,其中有一些标记,'W'是墙,'.'是可走的路,起点在左上角目标点在右下角ACM从左上角出发,只能向下和向右走,游戏要你找出有多少种不同的走法。很有压力吧?那是对于非计算机专业的人来说!你怎么看?试试吧。

输入

首先输入一个整数T,表示接下来有T(0<T<=10)个测试实例。

每组测试实例第一行是两个整数n(0<n<=10)和m(0<m<=10),表示游戏是在一张n*m的迷宫图上进行,接下来是一个n*m的迷宫图。

具体输入见样例。

输出

每组样例输出一个整数,表示ACM有多少种不同的走法。

具体输出见样例。

样例输入

复制
2
2 2
.w
.w
3 3
...
w..
...

样例输出

复制
0
3

提示


			

来源