2018 Wannafly summer camp Day3--Knight

Knight 题目描述： 有一张无限大的棋盘，你要将马从(0,0)(0,0)(0,0)移到(n,m)(n,m)(n,m)。 每一步中，如果马在(x,y)(x,y)(x,y)(x,y)(x,y)(x,y),你可以将它移动到 (x+1,y+2)(x+1,y+2)(x+1,y+2)(x+1,y+2)(x+1,y+2)(x+1,y+2), (x+1,y−2)(x+1,y−2)(x+1,y−2)(x+1,y−2)(x+1,y-2)(x+1,y−2),(x−1,y+2)(x−1,y+2)(x−1,y+2)(x−1,y+2)(x-1,y+2)(x−1,y+2),(x−1,y−2)(x−1,y−2)(x−1,y−2)(x−1,y−2)(x-1,y-2)(x−1,y−2), (x+2,y+1)(x+2,y+1)(x+2,y+1)(x+2,y+1)(x+2,y+1)(x+2,y+1),(x+2,y−1(x+2,y−1)(x+2,y−1(x+2,y−1)(x+2,y-1(x+2,y−1),(x−2,y+1)(x−2,y+1)或(x−2,y−1)(x−2,y−1)(x−2,y+1)(x−2,y+1)或(x−2,y−1)(x−2,y−1)(x-2,y+1)(x−2,y+1)或(x-2,y-1)(x−2,y−1)。 你需要最小化移动步数。 输入： 第一行一个整数tt表示数据组数 (1≤t≤1000)(1≤t≤1000)(1\leq t\leq 1000)。

每组数据一行两个整数n,m(|n|,|m|≤109)n,m(|n|,|m|≤109)n,m (|n|,|m| \leq 10^9)。

输出： 每组数据输出一行一个整数表示最小步数。 样例输入 2 0 4 4 2 样例输出 2 2

• 由于数据有10910910^9，所以BFS被毙了(～￣▽￣)～，没想到什么好的做法，所以BFS打表找规律=￣ω￣=。
• 打表结果及代码

这里写图片描述

#include<iostream>
#include <queue>
using namespace std;
int dir[8][2] = {
    {1,2},{1,-2},{-1,2},{-1,-2},
    {2,1},{2,-1},{-2,1},{-2,-1}
};
int n, m;
int maze[1100][1100];
bool vis[1100][1100];
struct Point {
    int x, y, step;
    Point(int _x, int _y, int _step) :
        x(_x), y(_y), step(_step) {}
};
void bfs(int sx, int sy)
{
    queue<Point>q;
    q.push(Point(sx, sy, 0));
    vis[sx][sy] = 1;
    maze[sx][sy] = 0;
    while (!q.empty())
    {
        int x = q.front().x;
        int y = q.front().y;
        int step = q.front().step;
        maze[x][y] = step;
        q.pop();
        for (int i = 0; i < 8; i++)
        {
            int tx = x + dir[i][0];
            int ty = y + dir[i][1];
            if (!vis[tx][ty]&&tx<61&&ty<61&&tx>=0&&ty>=0)
            {
                q.push(Point(tx, ty, step + 1));
                vis[tx][ty] = 1;
            }
        }
    }
}
int main() {
    //freopen("1.txt", "w", stdout);
    bfs(30, 30);
    for (int i = 0; i < 60; i++) {
        for (int j = 0; j <60; j++) {
            cout << maze[i][j] << " ";
        }
        cout << endl;
    }
    return 0;
}

• 从上面看，很明显是有规律的，据说大佬能一眼就看出来，以前我是不信的，直到现场有dalao花了4分钟拿了一血……<@_@>蒟蒻只能慢慢推了。首先先把上面的数据放到Excel里面，先预处理一下，将每个答案作为点，以起点为原点建立平面直角坐标系，结果如下：

这里写图片描述

之前我犯了一个错误，BFS起点放到数组边界上去了，应该放到偏中心的位置，把表打出来。将答案统一起来看，从2开始，所有相同的答案围成了一个八边形，这个八边形与坐标轴平行的边都是4层，不平行的都是3层，同时答案基本是向外递增的这样看的时候会发现两个特殊的地方，一个是(0,1),(1,0),(−1,0),(0,−1)(0,1),(1,0),(−1,0),(0,−1)(0,1),(1,0),(-1,0),(0,-1)这四个点为3，(2,0),(0,2),(0,−2),(−2,0)(2,0),(0,2),(0,−2),(−2,0)(2,0),(0,2),(0,-2),(-2,0)着四个点4，所以将这些点加入特判。 不难看出，这个表关于坐标轴对称(图中蓝色线)，同时也关于y=+−xy=+−xy=+-x对称(图中橙色线)，所以xxx轴正半轴为起点，逆时针划分为8个区域，每个区域都一样，只需要考虑1号区域就行了。 现在考虑的为1号区域，希望找到递增的答案之间存在的关系，这个关系为y=x/2y=x/2y=x/2 ,可以发现这条直线上的整点正好是答案的递增：（0，0）−>(2,1)−>(4,2).....−>(x,floor(x/2))（0，0）−>(2,1)−>(4,2).....−>(x,floor(x/2))（0，0）->(2,1)->(4,2).....->(x,floor(x/2))。将这条直线画出来。（floor()是对一个数值向下取整） 现在看y=x/2y=x/2y=x/2下方的点，满足关系y<x/2y<x/2y<x/2,也就是y<x−yy<x−yy<x-y(精度问题，计算时应该用double)，而且下方的点都是在刚才所说的八边形的4层边上，所以可以发现将这些点作如下变换后可以将横坐标和y=x/2对应y=x/2对应y=x/2对应:

double(x-y-y)/4.0*2;

最后将上面这个值取反+x−y+x−y+x-y就是答案。同理可以推出y=x/2y=x/2y=x/2上方的点，满足关系y>x/2y>x/2y>x/2,在刚才所说的八边形的3层边上，最后推出

double(x-y-y)/3.0*2;

• Code

#include <cstdio>
#include <cstring>
#include <cmath>
#include<algorithm>
#include<iostream>
#include<queue>
using namespace std;
typedef long long ll;
ll fun(ll x, ll y) {

    if (x == 1 && y == 0) {
        return 3;
    }
    if (x == 2 && y == 2) {
        return 4;
    }
    ll delta = x - y;
    if (y>delta) {
        return delta - 2 * floor(((double)(delta-y)) / 3.0);
    }
    else {
        return delta - 2 * floor(((double)(delta-y)) / 4.0);
    }
}

int main()
{

    int t;
    cin >> t;
    while (t--)
    {
        ll x, y;
        cin >> x >> y;
        x = abs(x);
        y = abs(y);
        if (x < y) {
            swap(x, y);
        }
        cout << fun(x, y) << endl;
    }

    return 0;
}

• 最后，为正经题解 Knight： 不妨假设x>=y>=0x>=y>=0x>=y>=0。 当x<=2yx<=2yx<=2y 时，定义每一步的冗余值wi=3−dx−dywi=3−dx−dyw_i=3-dx-dy， 那么Σwi=Σ(2−dx)=3Σwi=Σ(2−dx)=3Σ{w_i}=Σ(2-dx)=3*步数−x−y−x−y-x-y，显然我们只需要最小化冗余值。 我们先只用(+2,+1)(+2,+1)(+2,+1)(若x 为奇数则加一步(+1,+2))(+1,+2))(+1,+2))走到(x,y′)(x,y′)(x,y’)， 然后通过将(+2,+1)(+2,+1)(+2,+1)替换为2 个(+1,+2)(+1,+2)(+1,+2)使得0<=y−y′<30<=y−y′<30<=y-y’<3。 若y−y′=0y−y′=0y-y’=0，则冗余值为000，显然最小。 若y−y′=1y−y′=1y-y’=1，则将(+1,+2)(+1,+2)(+1,+2)替换为(+2,+1)(+2,+1)(+2,+1)和(−1,+2)(−1,+2)(-1,+2) 或将222 个(+2,+1)(+2,+1)(+2,+1)替换为(+1,+2),(+1,+2),(+2,−1)(+1,+2),(+1,+2),(+2,−1)(+1,+2),(+1,+2),(+2,-1)， 冗余值为222，显然最小。 （此处需要特判(2,2)(2,2)(2,2)）若y−y′=2y−y′=2y-y’=2，则加上(+2,+1)(+2,+1)(+2,+1)和(−2,+1)(−2,+1)(-2,+1)， 冗余值为444，由于不存在冗余值为111的步，所以最小。 当x>2yx>2yx>2y 时，定义每一步的冗余值wi=2−dxwi=2−dxw_i=2-dx， 那么Σwi=Σ(2−dx)=2∗Σwi=Σ(2−dx)=2∗Σw_i=Σ(2-dx)=2*步数−x−x-x，显然我们只需要最小化冗余值。 我们先只使用(+2,+1)(+2,+1)(+2,+1)走到(2y,y)(2y,y)(2y,y)， 然后用(+2,+1)(+2,+1)(+2,+1)和(+2,−1)(+2,−1)(+2,-1)走到(x′,y)(x′,y)(x’,y)使得0<=x−x′<40<=x−x′<40<=x-x’<4。 若x−x′=0x−x′=0x-x’=0 则冗余值为000，显然最小。 若x−x′=1x−x′=1x-x’=1 则将之前的(+2,+1)(+2,+1)(+2,+1)改为(+1,+2)(+1,+2)(+1,+2)和(+2,−1)(+2,−1)(+2,-1), 冗余值为111，显然最小。 （此处需要特判(1,0)(1,0)(1,0)）若x−x′=2x−x′=2x-x’=2 则加上(+1,+2)(+1,+2)(+1,+2)和(+1,−2)(+1,−2)(+1,-2)， 冗余值为222，由x/2+yx/2+yx/2+y 的奇偶性可知最小。 若x−x′=3x−x′=3x-x’=3 则加上(+2,+1),(+2,+1),(−1,−2)(+2,+1),(+2,+1),(−1,−2)(+2,+1),(+2,+1),(-1,-2)，冗余值为3， 由x/2+yx/2+yx/2+y 的奇偶性可知最小。 时间复杂度O(t)O(t)O(t)