描述 Description
奶牛们在被划分成 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) 的奶牛可能经过的路径有哪些。
输入格式 InputFormat
第 1 行: 3 个用空格隔开的整数：N，M，T.
第 2..N+1 行: 第 i+1 行为 M 个连续的字符，描述了草地第 i 行各点的情况，保证 字符是’.‘和’’中的一个 第 N+2 行: 4 个用空格隔开的整数：R1，C1，R2，以及 C2.
输出格式 OutputFormat
第 1 行: 输出 S，含义如题中所述
样例输入 SampleInput
10 10 7
……..
..……
………
..…..
……….
...….
……….
...….**
……..
…***….
5 4 7 3
样例输出 SampleOutput
74
数据范围和注释 Hint
草地被划分成 4 行 5 列，奶牛在 6 秒内从第 1 行第 3 列走到了第 1 行第 5 列。
奶牛在 6 秒内从 (1,3) 走到 (1,5) 的方法只有一种（绕过她面前的树）。
来源 Source
Silver
代码 Code
记忆化搜索。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
struct point
{
int z,y,x;
}f[1000000];
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
char a[101][101];
int c[101][101][16];
bool b[101][101][16];
int i,j,t,n,m,l,r,k,z,y,x,sx,sy,ex,ey,ans;
void TEST()
{
int i,j,t;
for (i=1;i<=n;i++)
{
for (j=1;j<=m;j++) cout<<a[i][j];
cout<<endl;
}
cout<<endl;
}
int main()
{
scanf("%d%d%dn",&n,&m,&t);
for (i=1;i<=n;i++) scanf("%s",a[i]+1);
scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
memset(c,0,sizeof(c));
memset(b,false,sizeof(b));
l=0;r=l;f[l].x=sx;f[l].y=sy;f[l].z=0;
c[f[l].x][f[l].y][f[l].z]=1;
b[f[l].x][f[l].y][f[l].z]=true;
while (r>=l)
{
if (f[l].z>t) break;
for (i=1;i<=4;i++)
{
int tx=f[l].x+dx[i];
int ty=f[l].y+dy[i];
if (tx<=0 || ty<=0 || tx>n || ty>m || a[tx][ty]=='*') continue;
c[tx][ty][f[l].z+1]+=c[f[l].x][f[l].y][f[l].z];
if (!b[tx][ty][f[l].z+1])
{
b[tx][ty][f[l].z+1]=true;
f[++r].x=tx;f[r].y=ty;f[r].z=f[l].z+1;
}
}
l++;
}
printf("%d\n",c[ex][ey][t]);
return 0;
}