管道系统

成绩 0 开启时间 2013年02月21日 星期四 18:02
折扣 0.8 折扣时间 2013年02月28日 星期四 18:02
允许迟交 关闭时间 2013年02月28日 星期四 18:02
输入文件 paipe.in 输出文件 paipe.out

【问题描述

胖莫林是一只胖老鼠,他住在地下。地下有1条被抛弃的管道系统,它们连接着莫林的家和其他建筑物。一天,莫林穿过管道发现了一个大仓库,仓库里堆满了食物,他决定每天早上去这个仓库享受食物。莫林也喜欢在管道中旅行,他想知道从家到仓库有多少种不同的简单的路径(相同位置的路径只算一次)。
这个管道系统被看作一个矩阵,包含M*N个单元格,M是行数,N是列数。每个单元格包含图4.10.1中的一个管道。
在图4.10.1中的管道类型:
注意11和12不一样。在12中横管和竖管并不互相连接,但在11中,他们连接;0中没有管道。莫林的家和仓库都在这个黑客帝国之外,有一个入口可以让他从家进入管道,并且有一个出口通向仓库。进入入口之后,他无法在到达出口之前从管道中出去。
接下来在图4.10.2中的两幅图是最后两个测试数据的样本输入。
考虑到位置的提高并且出口在这个黑客帝国的分界线上,帮助莫林计算有多少条从入口到出口的简单路径。
【输入格式】
输入包含一些测试数据。
对于每组测试数据,第一行有2个整数M和N(1≤M,N≤6);
下面M行描述这个黑客帝国的管道系统,每行有N个1~14的数,代表每个单元格中的管道类型。
入口和出口的位置被描绘成一个R,C,D的立方。R和C是整数并且满足1≤R≤M,1≤C≤N。D是一个字符,它可能是“U”、“D”、“L”或“R”,表示位置在单元格(R,C)的上/下/左/右。
每组数据的最后一行是2个三倍数Rs、Cs、Ds、RT、CT、DT,表示入口和出口的方位。它保证入口和出口的位置不同,且他们都在黑客帝国的边界上(如果D是‘U’,那么R必定是1;如果D是‘D’,那么R必定是M;如果D是‘L’,那么C必定是1;如果D是‘R’,那么C必定是N)。
输入文件以EOF终止。
【输出格式】

   对于每组测试数据,在单行输出答案。

【输入样例】
输入文件名:paipe.in
1 1
1
1 1 L 1 1 R
2 2
11 11
11 11
1 1 U 1 1 L
3 3
6 4 0
5 13 2
6 3 0
1 1 U 2 3 R
3 3
0 1 0
5 12 4
6 10 7
1 2 U 3 3 D
输出文件名:paipe.out
0
1
1
2