洛谷P1535 [USACO08MAR]Cow Travelling S 题解

题目链接：P1535 [USACO08MAR]Cow Travelling S

题意：

奶牛们在被划分成 \(N\) 行 \(M\) 列（\(2 \leq N,M \leq 100\)）的草地上游走， 试图找到整块草地中最美味的牧草。

Farmer John 在某个时刻看见贝茜在位置 \((R_1, C_1)\)，恰好 \(T\)（\(0 \lt T \leq 15\)）秒后，FJ 又在位置 \((R_2, C_2)\) 与贝茜撞了正着。FJ 并不知道在这 \(T\) 秒内贝茜是否曾经到过 \((R_2, C_2)\)，他能确定的只是，现在贝茜在那里。

设 \(S\) 为奶牛在 \(T\) 秒内从 \((R_1, C_1)\) 走到 \((R_2, C_2)\) 所能选择的路径总数，FJ 希望有 一个程序来帮他计算这个值。每一秒内，奶牛会水平或垂直地移动 \(1\) 单位距离（奶牛总是在移动，不会在某秒内停在它上一秒所在的点）。草地上的某些地方有树，自然，奶牛不能走到树所在的位置，也不会走出草地。

现在你拿到了一张整块草地的地形图，其中 . 表示平坦的草地，* 表示挡路的树。你的任务是计算出，一头在 \(T\) 秒内从 \((R_1, C_1)\) 移动到 \((R_2, C_2)\) 的奶牛可能经过的路径有哪些。

一眼看成组合数有救吗

注意到这是个计数dp

设 \(f_{i,j,k}\) 表示用 \(k\) 步恰好走到 \((i,j)\) 的方案数

这里要用记搜来算dp，刷表法更新（也就是用当前结点的答案去更新别的结点）

为什么用记忆化搜索呢？因为朴素的循环无法保证dp计算的顺序

时间复杂度的宽松上界为 \(O(nmt)\)

这题数据范围比较小所以据说暴搜剪枝都能过

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <queue>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(115)
int n,m,t,xa,ya,xb,yb,f[N][N][25];
char s[N][N];
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
struct node
{
    int x,y,step;
};
queue<node> q;
bool safe(int x,int y)
{
    return 1<=x&&x<=n&&1<=y&&y<=m&&s[x][y]!='*';
}
void bfs()
{
    q.push({xa,ya,0});
    f[xa][ya][0]=1;
    while(!q.empty())
    {
        node tmp=q.front();q.pop();
        for(int i=0; i<4; i++)
        {
            int tx=tmp.x+dx[i];
            int ty=tmp.y+dy[i];
            int ts=tmp.step+1;
            if(!safe(tx,ty)||ts>t)continue;
            if(f[tx][ty][ts])
            {
                f[tx][ty][ts]+=f[tmp.x][tmp.y][tmp.step];
                continue;
            }
            f[tx][ty][ts]+=f[tmp.x][tmp.y][tmp.step];
            q.push({tx,ty,ts});
        }
    }
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m >> t;
    for(int i=1; i<=n; i++)
        cin >> (s[i]+1);
    cin >> xa >> ya >> xb >> yb;
    bfs();
    cout << f[xb][yb][t] << '\n';
    return 0;
}