hzCPPOJ

走迷宫2

时间限制:  1 s      内存限制:   128 MB
提交:86     正确:60     分值:91

题目描述

假设有一个网格迷宫,由n行m列的单元格构成,每个单元格要么是空地,用“.”表示,要么是障碍物,用“*”表示。

给定起点(x0, y0)和终点坐标(x1, y1),探险家从起点出发,只能走垂直或者水平路线,不能斜着走,问: 每个单元格最多经过1次,有多少种从起点坐标到终点坐标的方案

(1,1)坐标位于左上角,(n,m)位于右下角。

输入

第1行:  6个由空格隔开的整数: n, m,x0, y0, x1, y1(1 <= x0, x1 <= n<=10, 1 <= y0, y1 <= m<=10)
第2到第n+1行:  数据的第n+1行由m个字符(" ." 表示空地," *" 表示障碍物),描述迷宫的 第n行。

如:
3 5 1 1 3 5 
.*...
.*...
...*.

输出

输出一个整数,每个单元格最多经过1次,有多少种从起点坐标到终点坐标的方案数

样例

样例输入:
3 5 1 1 3 5 .*... .*.*. ...*.
样例输出:
1
样例输入:
3 5 1 1 3 5 .*... .*... ...*.
样例输出:
4

提交人

lixun2017

来源/分类