Luogu p1535 [usaco08mar]cow traveling s problem solution

Luogu P1535 [USACO08MAR]Cow Travelling S Answer key

Topic link ：P1535 [USACO08MAR]Cow Travelling S

The question ：

Cows are being divided into $N$ That's ok $M$ Column （$2\le N,M\le 100$） Walk on the grass , Trying to find the most delicious grass in the whole grassland .

Farmer John At some point I saw Bessie in position $(R_1,C_1)$, just $T$（$0<T\le 15$） Seconds later ,FJ In position again $(R_2,C_2)$ Hit Bessie .FJ I don't know here $T$ Has Bessie ever been there in seconds $(R_2,C_2)$, All he can be sure of is , Now Bessie is there .

set up $S$ For cows in $T$ Seconds from $(R_1,C_1)$ Go to the $(R_2,C_2)$ The total number of paths that can be selected ,FJ Hope to have A program to help him calculate this value . Every second , Cows move horizontally or vertically $1$ Unit distance （ Cows are always moving , It won't stop at the point of the last second in a second ）. There are trees in some places on the grass , natural , Cows can't go where the tree is , Will not go out of the grass .

Now you have got a topographic map of the whole grassland , among . It means flat grass ,* A tree in the way . Your task is to figure out , At the end of $T$ Seconds from $(R_1,C_1)$ Move to $(R_2,C_2)$ What are the possible paths that cows of .

At a glance, can a combined number be saved

Notice that this is a count dp

set up $f_{i,j,k}$ To express with $k$ Step just to $(i,j)$ Number of alternatives

Here we need to use search to calculate dp, Brush table method update （ That is to use the answer of the current node to update other nodes ）

Why use memory search ？ Because the simple cycle cannot guarantee dp The order of calculation

The relaxed upper bound of time complexity is $O(nmt)$

The data range of this question is relatively small, so it's said that you can pass the storm search and pruning

Code ：

#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;
}

Reprint please explain the source