记忆化搜索经典问题：给定一张地图（有不能走的点）和时间t：给定4个数，分别是起点x1,y1，终点x2,y2
问有多少走法（地图点的个数小于10^4)

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 110, INF = 0x3f3f3f3f;

int n, m, k;
char g[N][N];
int f[N][N][20];//走到i，j这个点用了k秒的方案数
int stx, sty, edx, edy;

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

bool check(int x, int y)
{
    return (x > 0 && y > 0 && x <= n && y <= m);
}

int dfs(int a, int b, int sum)
{
    if(f[a][b][sum]) return f[a][b][sum];//如果走过了，直接返回当前值
    if(abs(edx - a) + abs(edy - b) > k - sum) return f[a][b][sum] = 0;//剪枝2：利用哈夫曼距离来判断在规定时间内还走不走得到
    if(sum > k) return f[a][b][sum] = 0;

    if(sum == k)
    {
        if(a == edx && b == edy) return f[a][b][sum] = 1;
        else return f[a][b][sum] = 0;
    }

    int ans = 0;
    for(int i = 0; i < 4; i ++)
    {
        int x = dx[i] + a, y = dy[i] + b;
        if(check(x, y) && g[x][y] != '*') 
            ans += dfs(x, y, sum + 1);
    }
    return f[a][b][sum] = ans;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> k;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            cin >> g[i][j];

    cin >> stx >> sty >> edx >> edy;

    cout << dfs(stx, sty, 0) << endl;
    return 0;
}