F - Main Street【 AtCoder Beginner Contest 258】

F - Main Street——AtCoder Beginner Contest 258

题目

多组数据，每组数据，给定 B，K，Sx，Sy，Gx，Gy。在一个二维平面上，每次可以上下左右移动一个单位，要从起点（Sx，Sy）移动到终点（Gx，Gy）。

有大路和小路两种路。大路是 [公式] （t 为任意整数）， [公式] 对应的直线。不在这些直线上的路是小路。走大路每移动一个单位花费 1 单位时间，走小路每移动一个单位花费 K 单位时间。（翻译摘自知乎用户樱落三千
https://zhuanlan.zhihu.com/p/536948831）

思路

1、直接求曼哈顿距离 这种情况不走主干道
2、尽量的走主干道，那么这时就要一开始就走主干道，如果起点终点都不在主干道，那么讨论的情况就是 4 * 4 = 16种

细节很多，在走主干道的时候，还需要讨论两点是不是在两个相邻主干道之间。这个时候可能不可以直接用曼哈顿距离计算，详看注释。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
#define ll long long

#define pii pair<ll, ll>

// b is main road, k is usual road's cost;
// start and end
ll b, k, sx, sy, gx, gy;

// 走到最近的捷径上
pii work(int x, int y, int op)
{
    switch (op)
    {
    case 0:
        x -= x % b;
        break;
    case 1:
        x += b - x % b;
        break;
    case 2:
        y -= y % b;
        break;
    default:
        y += b - y % b;
        break;
    }
    return {x, y};
}

void solve()
{
    cin >> b >> k >> sx >> sy >> gx >> gy;
    // 1、不走捷径 直接曼哈顿距离
    ll ans = (abs(sx - gx) + abs(sy - gy)) * k;
    // 2、 枚举四个起点个四个终点 共16种走捷径的方案
    for (int i = 0; i < 4; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            ll cnt = 0;
            auto [sx1, sy1] = work(sx, sy, i);
            auto [gx1, gy1] = work(gx, gy, j);
            cnt += (abs(sx - sx1) + abs(sy - sy1) + abs(gx - gx1) + abs(gy - gy1)) * k; // 起点终点走到捷径的距离
            // 如果两个点在同一个两捷径间空隙，这时不能使用曼哈顿距离直接计算
            if (sy1 % b == 0 && gy1 % b == 0 && sx1 / b == gx1 / b)
            {
                ll r = sx1 % b + gx1 % b;
                if (gy1 != sy1)
                    cnt += abs(gy1 - sy1) + min(r, 2 * b - r);
                else
                    cnt += abs(sx1 - gx1);
            }
            else if (sx1 % b == 0 && gx1 % b == 0 && sy1 / b == gy1 / b)
            {
                ll r = sy1 % b + gy1 % b;
                if (sx1 != gx1)
                {
                    cnt += abs(sx1 - gx1) + min(r, 2 * b - r);
                }
                else
                {
                    cnt += abs(sy1 - gy1);
                }
            }
            else
            {
                // 可以直接极计算曼哈顿距离
                cnt += (abs(sx1 - gx1) + abs(sy1 - gy1));
            }
            ans = min(ans, cnt);
        }
    }
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}