GYM 101606 G.GentleBots（构造）

56 阅读 0 评论 37 点赞

我是靠谱客的博主清脆吐司，最近开发中收集的这篇文章主要介绍GYM 101606 G.GentleBots（构造），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Description

在三维空间有两个机器人，他们的起点和终点都是整点且互不相同，他们每次只能在某一维坐标移动一个单位或者不动，要求两个机器人在运动过程中不能走到同一点，一个机器人也不能走向另一个机器人所在的位置，两个机器人同时运动，要求在不超过 7000 7000 次移动之后两个机器人无冲突的到达各自的终点，输出他们每一步的坐标

Input

两行分别六个整数表示两个机器人的起点坐标和终点坐标，坐标绝对值不超过 1000 1000

Output

输出不超过 7000 7000 行，每行输入六个整数表示每步两个机器人的坐标，要求运动过程中机器人坐标不超过 106 10 6 且无冲突

Sample Input

0 0 0 2 2 2
1 1 2 0 0 0

Sample Output

(0 0 0) (1 1 2)
(1 0 0) (1 1 1)
(1 1 0) (0 1 1)
(1 1 1) (0 1 0)
(1 1 2) (0 0 0)
(1 2 2) (0 0 0)
(2 2 2) (0 0 0)

Solution

依次考虑三维坐标 x,y,z x , y , z 让两个机器人到达终点，以考虑 x x 坐标为例，为避免两个机器人在运动过程中发生冲突，如果两个机器人的 $y, z$ 坐标都相同，则先让一个机器人的 y y 坐标或 $z$ 坐标移动一单位，之后两个机器人就必然不会发生冲突，直接朝着各自终点的 x x 坐标移动，最后把之前被移动了的机器人再移动回去即可，如此至多 $6000 + 6$ 次即可到达终点

Code

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const int INF=0x3f3f3f3f,maxn=100001;
struct node
{
int x[3];
}a,A,b,B;
void out()
{
printf("(%d %d %d) (%d %d %d)n",a.x[0],a.x[1],a.x[2],b.x[0],b.x[1],b.x[2]);
}
void Solve(int i,int j,int k)
{
int u=A.x[i]>a.x[i]?1:-1,v=B.x[i]>b.x[i]?1:-1,flag=0;
if(a.x[j]==b.x[j]&&a.x[k]==b.x[k])
{
flag=1;
a.x[j]--;
out();
}
while(a.x[i]!=A.x[i]||b.x[i]!=B.x[i])
{
if(a.x[i]!=A.x[i])a.x[i]+=u;
if(b.x[i]!=B.x[i])b.x[i]+=v;
out();
}
if(flag)
{
a.x[j]++;
out();
}
}
int main()
{
scanf("%d%d%d",&a.x[0],&a.x[1],&a.x[2]);
scanf("%d%d%d",&A.x[0],&A.x[1],&A.x[2]);
scanf("%d%d%d",&b.x[0],&b.x[1],&b.x[2]);
scanf("%d%d%d",&B.x[0],&B.x[1],&B.x[2]);
out();
Solve(0,1,2);
Solve(1,2,0);
Solve(2,0,1);
return 0;
}