#P1535. [USACO08MAR] Cow Travelling S
[USACO08MAR] Cow Travelling S
题目描述
奶牛们在被划分成 行 列()的草地上游走, 试图找到整块草地中最美味的牧草。
Farmer John 在某个时刻看见贝茜在位置 ,恰好 ()秒后,FJ 又在位置 与贝茜撞了正着。FJ 并不知道在这 秒内贝茜是否曾经到过 ,他能确定的只是,现在贝茜在那里。
设 为奶牛在 秒内从 走到 所能选择的路径总数,FJ 希望有 一个程序来帮他计算这个值。每一秒内,奶牛会水平或垂直地移动 单位距离(奶牛总是在移动,不会在某秒内停在它上一秒所在的点)。草地上的某些地方有树,自然,奶牛不能走到树所在的位置,也不会走出草地。
现在你拿到了一张整块草地的地形图,其中 .
表示平坦的草地,*
表示挡路的树。你的任务是计算出,一头在 秒内从 移动到 的奶牛可能经过的路径有哪些。
输入格式
第一行包含 个用空格隔开的整数:。
接下来 行:第 行为 个连续的字符,描述了草地第 行各点的情况,保证字符是 .
和 *
中的一个。
最后一行 个整数 。
输出格式
输出从 移动到 的方案数。
4 5 6
...*.
...*.
.....
.....
1 3 1 5
1
提示
奶牛在 秒内从 走到 的方法只有一种,绕过她面前的树。