迷路の小L

NC214320. 迷路の小L

描述

小 $\text L$ 说自己很喜欢跑步。
小 $\text{D}$ 把小 $\text L$ 跑步的地方抽象成一个 $\mathop n$ 行 $\mathop m$ 列的平面矩形，其中左上角为点 $(\text 1,1)$ ，右下角为点 $\text(n,m)$ 。对于每一个点 $\text(i,j)$ ，都有一个值 $a_{i,j}$ ， $a_{i,j}=1$ 表示该点为墙， $a_{i,j}=0$ 表示该点可以通过；一共有 $\mathop s$ 个点是墙，即 $s=\sum\limits_{i=1}^n\sum\limits_{j=1}^m a_{i,j}$ 。特别地，边界上的点 $\big($ 满足 $i=\text 0$ 或 $i=n+\text 1$ 或 $j=\text 0$ 或 $j=m+\text 1$ 的点 $\text(i,j)$ $\big)$ 也视作墙，但不计入 $\mathop s$ 。在地图上能且只能朝垂直和水平四个方向跑动。但是小 $\text L$ 很呆，总是迷路，因此一般只会沿一个方向跑动，当且仅当她撞墙时，她会改变方向（向后，向左或向右）跑动。
开始时小 $\text L$ 站在点 $\text(p,q)$ 。由于过多的撞墙会使得小 $\text L$ 变得更呆，可她又是如此热爱跑步，所以现在，小 $\text{D}$ 发出了 $\mathop T$ 次各自独立的询问，对于第 $\mathop i$ 次询问，他想知道小 $\text L$ 以 $\text(p,q)$ 为起点，最多能撞墙 $k_i$ 次时，最多能跑过多少个点。
注意，同一个点可以重复计数，起点也计数。在起点时可以向任意方向跑动。撞墙是指在当前点，若再沿原先方向跑动 $\text 1$ 步，所在点为墙；特殊地，若她在满足上述条件的点结束跑步，则不视为撞墙。

输入描述

输入共行。
第一行包含个正整数和个非负整数。
接下来行，每行包含个非负整数，其中第行第个数表示。
接下来行，第行包含一个非负整数。

输出描述

输出共行，第行包含一个正整数，表示对于第次询问，小最多能跑过的点数。

示例1

输入:

5 5 1 1 1 10
0 0 1 0 1
1 0 0 0 1
0 1 0 0 1
1 0 0 0 1
1 1 0 0 0
3

输出:

说明:

$(1,1)\to (1,2)（撞）\to (2,2)（撞）\to (2,4)（撞）\to (5,4)$ 。

示例2

输入:

5 5 1 3 1 10
0 0 1 0 1
1 0 0 0 1
0 1 0 0 1
1 0 0 0 1
1 1 0 0 0
10

输出:

说明:

很遗憾，但小 $\text L$ 不能跑。注意，在同一点内多次改变方向时，该点并不会被重复计数，因为小 $\text L$ 不能用转圈代替跑步。

上次编辑到这里，代码来自缓存点击恢复默认模板

C++(clang++11) 解法, 执行用时: 163ms, 内存消耗: 133112K, 提交时间: 2021-02-03 20:36:56

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f3f3f3f3fll
const int N=1005;
typedef long long ll;
int n,m,s,tot,T,p,q,a[N][N];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
int vis[N][N],num,head[4*N],nex[N*N],to[N*N],wi[N*N];
ll f[4*N][4*N],mx[4*N];
void add(int u,int v,int w){to[++num]=v;nex[num]=head[u];head[u]=num;wi[num]=w;}
void go(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int xx=x,yy=y;
        while(!a[xx+dx[i]][yy+dy[i]])
            xx+=dx[i],yy+=dy[i];
        if(xx==x&&yy==y) continue;
        if(!vis[xx][yy])
        {
            vis[xx][yy]=++tot;
            go(xx,yy);
        }
        add(vis[x][y],vis[xx][yy],abs(x-xx)+abs(y-yy));
    }
}
int main()
{
    scanf("%d%d%d%d%d%d",&n,&m,&T,&p,&q,&s);
    for(int i=0;i<=n+1;i++)
        for(int j=0;j<=m+1;j++) a[i][j]=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        scanf("%d",&a[i][j]);
    vis[p][q]=++tot;
    go(p,q);
    assert(tot<=4000);
    memset(f,-inf,sizeof(f));
    f[1][0]=0;
    for(int i=0;i<=tot;i++)
        for(int j=1;j<=tot;j++)
        {
            if(f[j][i]==f[0][0]) continue;
            for(int k=head[j];k;k=nex[k])
            {
                int v=to[k];
                f[v][i+1]=max(f[v][i+1],f[j][i]+wi[k]);
            }
        }
    for(int i=1;i<=tot;i++)
        for(int j=head[i];j;j=nex[j])
        mx[i]=max(mx[i],1ll*wi[j]);
    while(T--)
    {
        int k;scanf("%d",&k);k++;
        ll ans=0;
        for(int i=1;i<=tot;i++)
        {
            if(k<=tot) ans=max(ans,f[i][k]);
            else ans=max(ans,f[i][tot]+(k-tot)*mx[i]);
        }
        printf("%lld\n",ans+1);
    }
}