思维+建图

首先,万物起源:
对于这种两个变动的题目,我们相对的看
可以给金的每次移动向前增加一位

然后我们在草稿上画出一个金可以走到的所有格点
会发现,正好以斜线为界限的范围是这个金可以走到的地方

但是,还有一个问题,这里是一轮过后,即金和步都走一步后
但是还有可能步还没走就让金吞了

因此,为了避免这种情况下的漏算,我们不妨拆点,对于每一个点
我们拆一个点正好在他头上。

然后我们遍历,连边
对于拆的点,我们原来的点不和他连边

但是,这样有一个问题:
即,如果出现了两个原来的点他们正好连着,即点b在点a的头上
那么我们就尴尬了

为了解决这个问题
我们换统计点权为统计边权
我们事先排序,在此之后我们再判断是否存在这种情况
如果存在这种情况,我们让a->b,权值为1,且让之后所有的连向b的点权值都赋为2
否则,我们拆点

然后还有一个坑点,就是,如果初始时,我们有一个点正好在金的正下方
那么我们最终的答案还要加上
(但是在代码中,我是连接金和这个点了)

#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int max_n = 10010;
const int max_m = 1e7;
struct edge
{
    int to,cost,next;
}E[max_m];
int head[max_n];
int cnt=1;
void add(int from,int to,int cost)
{
    E[cnt].to=to;
    E[cnt].cost=cost;
    E[cnt].next=head[from];
    head[from]=cnt++;
}
ll xs[max_n],ys[max_n];
int tot=0;
bool check(int i,int j)
{
    return ys[j]>ys[i] && llabs(xs[j]-xs[i])<=llabs(ys[j]-ys[i]);
}

int used[max_n];
int dfs(int u)
{
    if (used[u])return used[u];
    int ans=0;
    for (int i=head[u];i;i=E[i].next)
    {
        int v = E[i].to;
        ans=max(ans,E[i].cost+dfs(v));
    }
    return used[u]=ans;
}


int weights[max_n];
int help[max_n];
bool cmp(int a,int b)
{
    return xs[a]==xs[b]?ys[a]<ys[b]:xs[a]<xs[b];
}

int main()
{
    ios::sync_with_stdio(0);
    int T;cin>>T;
    while (T--)
    {
        tot=1;
        cin>>xs[tot]>>ys[tot];
        int n;cin>>n;
        for (int i=0;i<=n*2+100;++i)head[i]=used[i]=weights[i]=0,help[i]=i;
        cnt=1;
        for (int i=1;i<=n;++i)
        {
            ++tot;
            cin>>xs[tot]>>ys[tot];
        }

        sort(help+2,help+2+n);

        for (int _=2;_<=n;++_)
        {
            int i = help[_];
            int j = help[_+1];
            if (xs[i]==xs[j] && ys[i]==ys[j]-1)
            {
                weights[j]=1;
            }
            else
            {
                ++tot;
                xs[tot]=xs[i];
                ys[tot]=ys[i]+1;
                if (xs[tot]==xs[1] && ys[tot]==ys[1])
                {
                    add(1,tot,1);
                }
            }
        }

        for (int i=1;i<=tot;++i)
        {
            for (int j=1;j<=tot;++j)
            {
                if (llabs(ys[i]-ys[j])<=1 && xs[i]==xs[j])continue;
                if (check(i,j))
                {
                    add(i,j,1+weights[j]);
                }
            }
        }
        cout<<dfs(1)<<endl;
    }
}