拯救小Z
Time Limit : 3000/1000ms (Java/Other) Memory Limit : 65536/65536K (Java/Other)
Total Submission(s) : 43 Accepted Submission(s) : 14
Font: Times New Roman | Verdana | Georgia
Font Size: ← →
Problem Description
小Z是一个卓越的探险家，有一次，小Z在外探险的过程中，在一个N*M的迷宫中迷路了，现在小Z处于迷宫中的(x,y)点，迷宫的入口在(1,1)点。只有你沿着最短的路径找到小Z，小Z才会跟你离开迷宫。在迷宫中，你可以走上下左右四个方向。问有多少种走法可以拯救小Z？答案对1000000007取模(每种走法只要有一步不同即视为不同)
Input
第一行有一个整数T，代表T组数据。（1<=T<=10）
每组数据的第一行有两个整数N,M代表迷宫的大小。（2<=N,M<=500）
接下来N行每行有M个字符。（包括.和*，.代表可以行走的路，*代表不可以行走的墙。）
每组数据的最后一行有两个整数x,y代表小Z现在的位置。(1<=x<=N,1<=y<=M)
（数据保证(1,1)和(x,y)的位置都是.，保证坐标(x,y)不等于(1,1)）
每组数据的第一行有两个整数N,M代表迷宫的大小。（2<=N,M<=500）
接下来N行每行有M个字符。（包括.和*，.代表可以行走的路，*代表不可以行走的墙。）
每组数据的最后一行有两个整数x,y代表小Z现在的位置。(1<=x<=N,1<=y<=M)
（数据保证(1,1)和(x,y)的位置都是.，保证坐标(x,y)不等于(1,1)）
Output
对于每组数据，输出一行。
如果可以拯救小Z，输出可以拯救小Z的方案数,结果对1000000007取模。
如果不可以拯救小Z，输出-1。
如果可以拯救小Z，输出可以拯救小Z的方案数,结果对1000000007取模。
如果不可以拯救小Z，输出-1。
Sample Input
2 2 2 .. .. 2 2 2 2 .* *. 2 2
Sample Output
2 -1
Source
642超哥