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
#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;
}
之前我犯了一个错误,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;
#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;
}