A1227 游荡的奶牛

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

// 游荡的奶牛（A1227，与《Cow Travelling S》是同一道题）
//
// 分层 DP：f_t(r,c) = 从 (R1,C1) 出发走恰好 t 步到达 (r,c) 的走法数。
// 每一层由上一层的四个相邻格相加得到，答案就是 f_T(R2,C2)。
// 奶牛每秒必须走一格，可以重复经过同一个格子。
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // 滚动数组：pre 是上一层，cur 是当前层
    vector<vector<long long>> pre(n + 2, vector<long long>(m + 2, 0));
    vector<vector<long long>> cur(n + 2, vector<long long>(m + 2, 0));
    pre[r1][c1] = 1;

    for (int t = 1; t <= T; t++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                cur[i][j] = 0;
                if (mp[i][j] == '*') continue; // 有树的地方到不了
                cur[i][j] = pre[i - 1][j] + pre[i + 1][j] + pre[i][j - 1] + pre[i][j + 1];
            }
        }
        pre.swap(cur);
    }

    cout << pre[r2][c2] << "\n";
    return 0;
}