管道系统

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23: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