4477: P1535 [USACO08MAR] Cow Travelling S

奶牛们在被划分成 � N 行 � M 列（ 2 ≤ � , � ≤ 100 2≤N,M≤100）的草地上游走， 试图找到整块草地中最美味的牧草。 Farmer John 在某个时刻看见贝茜在位置 ( � 1 , � 1 ) (R 1 ,C 1 )，恰好 � T（ 0 < � ≤ 15 0

第一行包含 3 3 个用空格隔开的整数： � , � , � N,M,T。 接下来 � n 行：第 � i 行为 � M 个连续的字符，描述了草地第 � i 行各点的情况，保证字符是 . 和 * 中的一个。 最后一行 4 4 个整数 � 1 , � 1 , � 2 , � 2 R 1 ,C 1 ,R 2 ,C 2 。

输出从 ( � 1 , � 1 ) (R 1 ,C 1 ) 移动到 ( � 2 , � 2 ) (R 2 ,C 2 ) 的方案数。

4 5 6
...*.
...*.
.....
.....
1 3 1 5

1