Atcoder Beginner Contest 259 Problem D 题解

题目链接：https://atcoder.jp/contests/abc259/tasks/abc259_d

题目大意

现给定 $N$ 个在平面坐标系中的圆，第 $i$ 个圆圆心坐标为 $(X_i,Y_i)$ ，半径为 $R_i$ 。又给定两个坐标 $(S_x,S_y)$ 及 $(T_x,T_y)$ ，试求出可否从 $(S_x,S_Y)$ 出发且只经过给定圆的圆周可否到达点 $(T_x,T_y)$ 。

输入格式

对于每个测试点，第一行输 $N$ 入，第二行输入 $S_x,S_y,T_x,T_y$ ，其后 $N$ 行，每行输入 $X_i,Y_i,R_i$ 。

输出格式

如果能到达，输出" $Yes$ ";否则输出" $No$ "。

样例输入1

样例输出1

Yes

样例输入2

样例输出2

No

样例解释1

原图如下：

以下为从点 $(0,-2)$ 至点 $(3,3)$ 的走法之一。
1. 从点 $(0,-2)$ 经过给定的第一个圆可移动到点 $(1,- \sqrt 3)$ 。
2. 从点 $(1,- \sqrt 3)$ 经过给定的第二个圆可移动到点 $(2,2)$ 。
3. 从点 $(2,2)$ 经过给定的第三个圆可移动到点 $(3,3)$ 。

样例解释2

原图如下：

由图可知：
不可在只经过圆周的情况下从点 $(0,1)$ 移动至点 $(0,3)$ 。

解析

本题使用图论算法求解。
可将所有圆编号并视为一个点，若两个圆可相互到达，即可视为两点间存在一条边，以样例 $1$ 为例，则原图可化为一无向图，如下：

原问题可变化为：求点 $(0,-2)$ 与点 $(3,3)$ 是否联通。
以上问题可使用深度优先搜索算法进行求解。
综上，原问题解法为：先将原图转化为有向图后使用深度优先搜索算法判断起点与终点是否连通即可。

代码实现

以上算法代码实现如下：

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll b,k,sx,sy,gx,gy;
ll ask(){
    ll ans=k*(abs(sx-gx)+abs(sy-gy));
    ll sy_2=sy-sy%b,gy_2=gy-gy%b,sx_2=sx-sx%b,gx_2=gx-gx%b;
    for(auto [x_1,y_1]:{array{sx,sy_2},{sx,sy_2+b},{sx_2+b,sy},{sx_2,sy}}){
        for(auto [x_2,y_2]:{array{gx,gy_2},{gx,gy_2+b},{gx_2+b,gy},{gx_2,gy}}){
            ll res;
            if(x_1%b==0&&x_2%b==0&&y_1/b==y_2/b){
                int r=y_2%b+y_1%b;
                res=min((ll)abs(y_2-y_1)+(ll)abs(x_2-x_1)*k,(ll)min(abs(x_2-x_1)+r,(ll)abs(x_2-x_1)+2*b-r));
            }
            else if(y_1%b==0&&y_2%b==0&&x_1/b==x_2/b){
                int r=x_2%b+x_1%b;
                res=min((ll)abs(x_2-x_1)+(ll)abs(y_2-y_1)*k,(ll)min(abs(y_2-y_1)+r,(ll)abs(y_2-y_1)+2*b-r));
            }
            else{
                res=(ll)abs(x_2-x_1)+(ll)abs(y_2-y_1);
            }
            res+=k*(abs(x_1-sx)+abs(y_1-sy)+abs(x_2-gx)+abs(y_2-gy));
            ans=min(ans,res);
        }
    }
    return ans;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        scanf("%lld%lld%lld%lld%lld%lld",&b,&k,&sx,&sy,&gx,&gy);
        printf("%lld\n",ask());
    }
    return 0;
}