A8031.游荡的奶牛 全站最快解法

#include <iostream>
#include <vector>
#include <string>

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m, t;
    std::cin >> n >> m >> t;

    std::vector<std::string> grid(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> grid[i];
    }

    int r1, c1, r2, c2;
    std::cin >> r1 >> c1 >> r2 >> c2;
    r1--;
    c1--;
    r2--;
    c2--;

    if (r1 < 0 || r1 >= n || c1 < 0 || c1 >= m || r2 < 0 || r2 >= n || c2 < 0 || c2 >= m) {
        std::cout << 0 << '\n';
        return 0;
    }

    if (grid[r1][c1] == '*' || grid[r2][c2] == '*') {
        std::cout << 0 << '\n';
        return 0;
    }

    std::vector<std::vector<std::vector<long long>>> dp(
        t + 1, 
        std::vector<std::vector<long long>>(
            n, 
            std::vector<long long>(m, 0)
        )
    );

    dp[0][r1][c1] = 1;

    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    for (int time = 0; time < t; ++time) {
        for (int r = 0; r < n; ++r) {
            for (int c = 0; c < m; ++c) {
                if (dp[time][r][c] == 0) {
                    continue;
                }
                
                for (int i = 0; i < 4; ++i) {
                    int next_r = r + dr[i];
                    int next_c = c + dc[i];

                    if (next_r >= 0 && next_r < n && next_c >= 0 && next_c < m && grid[next_r][next_c] != '*') {
                        dp[time + 1][next_r][next_c] += dp[time][r][c];
                    }
                }
            }
        }
    }

    std::cout << dp[t][r2][c2] << '\n';

    return 0;
}