状态转移方程
首先，我们定义dp[i][x][y]表示在第I秒时到（x,y）时的可能路线数
那么，显而易见 dp[0][start_x][start_y]=1
且我们可知，每一个点（x，y）可以由四个点（x+1,y）（x-1,y）（x,y+1）（x,y-1）到达
那么，根据加法原理，易得：
dp[i][x][y]=dp[i-1][x+1][y]+dp[I-1][x-1][y]+dp[I-1][x][y+1]+dp[I-1][x][y-1]
时间复杂度
O(tmn)
代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int dp[16][105][105];
int n,m,t;
bool a[105][105];
int start_x,start_y,end_x,end_y;
const int addmove[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int main(){
cin>>n>>m>>t;
memset(a,true,sizeof(a));
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
char temp;
cin>>temp;
a[i][j]=!(temp=='*');
}
}
cin>>start_x>>start_y>>end_x>>end_y;
memset(dp,0,sizeof(dp));
dp[0][start_x][start_y]=1;
for(int i=1;i<=t;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=m;k++)
for(int p=0;p<4;p++){
if(!a[j][k])
dp[i][j][k]=0;
else
dp[i][j][k]+=dp[i-1][j+addmove[p][0]][k+addmove[p][1]];
}
cout<<dp[t][end_x][end_y];
}