stdKonjac's Blog

An AC a day keeps the WA away ~

【游荡的奶牛】

题目描述

奶牛们在被划分成 N 行 M 列(2 <= N <= 100; 2 <= M <= 100)的草地上游走,试图找到整块草地中最美味的牧草。Farmer John 在某个时刻看见贝茜在位置 (R1, C1),恰好 T(0<T<=15)秒后,FJ 又在位置 (R2, C2) 与贝茜撞了正着。FJ 并不知道在这T秒内贝茜是否曾经到过(R2, C2),他能确定的只是,现在贝茜在那里。

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

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

输入格式

第 1 行: 3 个用空格隔开的整数 N,M,T。
第 2~N+1 行:第 i+1 行为 M 个连续的字符,描述了草地第 i 行各点的情况,保证字符是 ‘.’ 和 ‘*’ 中的一个。
第 N+2 行:4 个用空格隔开的整数: R1,C1,R2,以及 C2。

输出格式

输出第 1 行:输出 S,含义如题中所述。

样例数据 1

输入

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

输出

1

备注

【样例说明】
草地被划分成 4 行 5 列,奶牛在 6 秒内从第 1 行第 3 列走到了第 1 行第 5 列。
奶牛在 6 秒内从 (1,3) 走到 (1,5) 的方法只有一种(绕过她面前的树)。

哎呀一开始以为100×100的图直接DFS就好了,结果只拿了30分……正解是动规做ans[i][j][k]表示在k时间走到(i,j)的方案数,显然是通过旁边四格看是否能转移过来,具体看代码:

点赞
  1. YYY说道:

    突然发现BFS和DP的代码似乎是一样的...

    1. UNknown说道:

      就是差不多……结果还是DP

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

This site uses Akismet to reduce spam. Learn how your comment data is processed.