#P1535. [USACO08MAR] Cow Travelling S

[USACO08MAR] Cow Travelling S

题目描述

奶牛们在被划分成 NNMM 列(2N,M1002 \leq N,M \leq 100)的草地上游走, 试图找到整块草地中最美味的牧草。

Farmer John 在某个时刻看见贝茜在位置 (R1,C1)(R_1, C_1),恰好 TT0<T150 \lt T \leq 15)秒后,FJ 又在位置 (R2,C2)(R_2, C_2) 与贝茜撞了正着。FJ 并不知道在这 TT 秒内贝茜是否曾经到过 (R2,C2)(R_2, C_2),他能确定的只是,现在贝茜在那里。

SS 为奶牛在 TT 秒内从 (R1,C1)(R_1, C_1) 走到 (R2,C2)(R_2, C_2) 所能选择的路径总数,FJ 希望有 一个程序来帮他计算这个值。每一秒内,奶牛会水平或垂直地移动 11 单位距离(奶牛总是在移动,不会在某秒内停在它上一秒所在的点)。草地上的某些地方有树,自然,奶牛不能走到树所在的位置,也不会走出草地。

现在你拿到了一张整块草地的地形图,其中 . 表示平坦的草地,* 表示挡路的树。你的任务是计算出,一头在 TT 秒内从 (R1,C1)(R_1, C_1) 移动到 (R2,C2)(R_2, C_2) 的奶牛可能经过的路径有哪些。

输入格式

第一行包含 33 个用空格隔开的整数:N,M,TN,M,T

接下来 nn 行:第 ii 行为 MM 个连续的字符,描述了草地第 ii 行各点的情况,保证字符是 .* 中的一个。

最后一行 44 个整数 R1,C1,R2,C2R_1,C_1,R_2,C_2

输出格式

输出从 (R1,C1)(R_1, C_1) 移动到 (R2,C2)(R_2, C_2) 的方案数。

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

提示

奶牛在 66 秒内从 (1,3)(1,3) 走到 (1,5)(1,5) 的方法只有一种,绕过她面前的树。