A1161 Cow Travelling S

#include <bits/stdc++.h>
using namespace std;

// Cow Travelling S（A1161，USACO08MAR）
//
// 状态 f(r,c,t)：从 (r,c) 出发走恰好 t 步到达 (R2,C2) 的方案数。
// 用记忆化搜索算 f(R1,C1,T)，并用曼哈顿距离剪枝。
// 奶牛每秒必须上下左右移动一格，可以重复经过同一个格子。
int n, m, T;
vector<string> mp;
int r1, c1, r2, c2;
long long memo[16][105][105];
bool seen[16][105][105];
const int dr[4] = {-1, 1, 0, 0};
const int dc[4] = {0, 0, -1, 1};

long long dfs(int r, int c, int t) {
    // 边界：没有步数了，只有站在终点才算一种方案。
    if (t == 0) return (r == r2 && c == c2) ? 1LL : 0LL;
    // 剪枝：曼哈顿距离都走不到终点，这一支直接没有方案。
    if (abs(r - r2) + abs(c - c2) > t) return 0;
    // 记忆化：同一个 (t,r,c) 只算一次。
    if (seen[t][r][c]) return memo[t][r][c];
    seen[t][r][c] = true;
    long long res = 0;
    for (int k = 0; k < 4; k++) {
        int nr = r + dr[k], nc = c + dc[k];
        if (nr < 1 || nr > n || nc < 1 || nc > m) continue; // 出界
        if (mp[nr][nc] == '*') continue;                      // 有树
        res += dfs(nr, nc, t - 1);
    }
    memo[t][r][c] = res;
    return res;
}

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

    cin >> n >> m >> T;
    mp.resize(n + 1);
    for (int i = 1; i <= n; i++) {
        string row;
        cin >> row;
        mp[i] = " " + row; // 列下标从 1 开始
    }
    cin >> r1 >> c1 >> r2 >> c2;

    cout << dfs(r1, c1, T) << "\n";
    return 0;
}