题解 P1535 【[USACO08MAR]Cow Travelling S】

kodiak · 2020-05-16 17:04:43 · 题解

题目数据是t<=15，大致计算一下，暴力bfs是4^{15}，会爆

那我们就把那15次移动拆成两半，最后再合在一起

这样时间复杂度大概是4^{\frac{t}{2}}

我们设tx[0][k][i][j]表示从起点走k次到达(i,j)的方案数，tx[1][k][i][j]为从终点起走k次到(i,j)的方案数

则我们在路径上第k秒经过(i,j)到达终点的方案数就是tx[0][k][i][j]\times tx[1][t-k][i][j]

所以ans=\sum\limits_{i=1}^n\sum\limits_{j=1}^mtx[0][k][i][j]\times tx[1][t-k][i][j]

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int tx[2][10][110][110];
queue<int>qux;
queue<int>quy;
queue<int>qut;
int vis[10][110][110];
int maps[110][110];
int n,m;
void bfs(int sx,int sy,int ty,int tme)
{
    memset(vis,0,sizeof(vis));
    qux.push(sx);
    quy.push(sy);
    qut.push(0);
    vis[0][sx][sy]=1;
    tx[ty][0][sx][sy]=1;
    while(!qux.empty())
    {
        int x=qux.front(),y=quy.front(),t=qut.front();
        qux.pop();
        quy.pop();
        qut.pop();
        if(t>tme)
        {
            continue;
        }
        if(x!=1&&maps[x-1][y]==0)
        {
            tx[ty][t+1][x-1][y]+=tx[ty][t][x][y];
            if(!vis[t+1][x-1][y])
            {
                vis[t+1][x-1][y]=1;
                qux.push(x-1);
                quy.push(y);
                qut.push(t+1);
            }
        }
        if(y!=1&&maps[x][y-1]==0)
        {
            tx[ty][t+1][x][y-1]+=tx[ty][t][x][y];
            if(!vis[t+1][x][y-1])
            {
                vis[t+1][x][y-1]=1;
                qux.push(x);
                quy.push(y-1);
                qut.push(t+1);
            }
        }
        if(x!=n&&maps[x+1][y]==0)
        {
            tx[ty][t+1][x+1][y]+=tx[ty][t][x][y];
            if(!vis[t+1][x+1][y])
            {
                vis[t+1][x+1][y]=1;
                qux.push(x+1);
                quy.push(y);
                qut.push(t+1);
            }
        }
        if(y!=m&&maps[x][y+1]==0)
        {
            tx[ty][t+1][x][y+1]+=tx[ty][t][x][y];
            if(!vis[t+1][x][y+1])
            {
                vis[t+1][x][y+1]=1;
                qux.push(x);
                quy.push(y+1);
                qut.push(t+1);
            }
        }
    }
}
signed main()
{
    int t;
    cin>>n>>m>>t;
    for(int i=1;i<=n;i++)
    {
        char ch[200];
        scanf("%s",ch+1);
        for(int j=1;j<=m;j++)
        {
            maps[i][j]=ch[j]=='*';
        }
    }
    int r1,c1,r2,c2;
    cin>>r1>>c1>>r2>>c2;
    int key=7;
    if(t<=key)
    {
        bfs(r1,c1,0,t);
        cout<<tx[0][t][r2][c2];
    }
    else
    {
        bfs(r1,c1,0,key);
        bfs(r2,c2,1,t-key);
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                ans+=tx[0][key][i][j]*tx[1][t-key][i][j];
            }
        }
        cout<<ans;
    }
}