F – False God

题目描述：

你有一个金将，对面有n个步兵，金将每回合可以移动到如下的六个格子中任意一个

步兵只能往下移动，且每回合都必须往下移动一格

无论是金将碰到步兵，还是步兵碰到金将，步兵都会被吃掉，问金将最多能吃多少个步兵，棋盘无限大

思路：

非常巧妙的一个题

显然可以发现如果有步兵的y小于金将的y，就永远都吃不到他

且步兵之间的位置是相对不变的!

假设金将的位置是(x0, y0)，想吃掉位于(x, y)的位置的步兵，就必须满足 $abs(x0-x) >= y - y0 + 1$,也就是金将横向移动的距离必须小于等于步兵到金将的纵向距离 + 1，这样才能在步兵移动到金将下面之前遇到他

所以点 (xi, yi)能否到达点 (xj, yj)的判断方法是： $abs(x_i - x_i) <= y_j - y_j + 1$

所以我们可以 $n^2$ 地进行暴力，进行建图，会行成一颗以金将为根的树，问题就转换成求树上的最长路

//Work by: Chelsea
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 30000 + 50
int n, m, k, op;
struct ran{
    int x, y;
}tr[MAX];
vector<int>vv[MAX];
int dis[MAX];

int dfs(int u, int fa){
    if(dis[u])return dis[u];
    dis[u] = 1;
    for(auto v : vv[u]){
        dis[u] = max(dis[u], dfs(v, u) + 1);
    }
    return dis[u];
}

void work(){
    cin >> tr[0].x >> tr[0].y;
    cin >> n;
    for(int i = 1; i <= n; ++i)cin >> tr[i].x >> tr[i].y;
    for(int i = 0; i <= n; ++i){
        vv[i].clear();
        mem(dis, 0);
        for(int j = 1; j <= n; ++j){
            if(i == j)continue;
            if(abs(tr[i].x - tr[j].x) <= tr[j].y - tr[i].y + 1)vv[i].push_back(j);
        }
    }
    cout << dfs(0, -1) - 1 << endl;
}


int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}