Searching for the very best grass, the cows are travelling about the pasture which is represented as a grid with N rows and M columns (2 <= N <= 100; 2 <= M <= 100). Keen observer Farmer John has recorded Bessie's position as (R1, C1) at a certain time and then  as (R2, C2) exactly T (0 < T <= 15) seconds later. He's not sure if she passed through (R2, C2) before T seconds, but he knows she is there at time T. FJ wants a program that uses this information to calculate an integer S that is the number of ways a cow can go from (R1, C1) to (R2, C2) exactly in T seconds. Every second, a cow can travel from any position to a vertically or horizontally neighboring position in the pasture each second (no resting for the cows). Of course, the pasture has trees through which no cow can travel. Given a map with '.'s for open pasture space and '*' for trees, calculate the number of possible ways to travel from (R1, C1) to
(R2, C2) in T seconds.

* Line 1: Three space-separated integers: N, M, and T
* Lines 2..N+1: Line i+1 describes row i of the pasture with exactly M
characters that are each '.' or '*'
* Line N+2: Four space-separated integers: R1, C1, R2, and C2.

* Lines 1: A single line with the integer S described above.

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

1

题目分析：

题目给你一个图 起点终点 和时间T 问你从起点到终点消耗时间为T的方案数
SB递推 三重循环搞定

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
bool map[105][105];
char s[105];
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
int n,m,T,lx,ly,rx,ry,f[16][105][105];
int main()
{
    scanf("%d%d%d",&n,&m,&T);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",&s[0]);
        for(int j=0;j<m;j++)
            map[i][j+1]=(s[j]=='*')?0:1;
    }
    scanf("%d%d%d%d",&lx,&ly,&rx,&ry);
    f[0][lx][ly]=1;
    for(int k=1;k<=T;k++) 
        for(int i=1;i<=n;i++) 
            for(int j=1;j<=m;j++)
                if(map[i][j])
                    for(int z=1;z<=4;z++)
                    {
                        int dxx=i+dx[z],dyy=j+dy[z];
                        if(dxx>=1&&dxx<=n&&dyy>=1&&dyy<=m&&map[dxx][dyy])
                            f[k][i][j]+=f[k-1][dxx][dyy];
                    }
    printf("%d",f[T][rx][ry]);
}