遭遇战
【问题描述】 小林和小华在一个 n*n 的矩形方格里玩游戏，矩形左上角为（0,0），右下角为（n-1，n1）。两人同时进入地图的随机位置，并以相同速度进行走位。为了隐蔽性，两人都不会再走 自己走过的格子。如果两人向某一方向前进，那么他们会跑到不能跑为止，当不能跑的时候， 小林会向右转，小华则会向左转，如果不能跑，则不再动。 现在已知两人进入地图的初始 位置和方向，请算出两人遭遇的位置。
【输入】 第一行一个正整数 t，表示测试数据的组数。 接下来的 t 组数据，每组数据的第一行包含 1 个整数 n，。 第二行包含三个整数，x、y 和 d，表示小林的初始位置和一开始跑的方向。其中 d=0 表 示东；d=1 表示南；d=2 表示西；d=3 表示北。 第三行与第二行格式相同，但描述的是小华。
【输出】 输出 t 行，若会遭遇，则包含两个整数，表示他们第一次相遇的格子的坐标，否则输出 “-1”。
【输入输出样例】
fight.in
2
2
0 0 0
0 1 2
4
0 1 0
3 2 0
fight.out
-1
1 3
【数据范围】 对于全部的数据，保证有 1<=t<=10，1<=n<=1000。
#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
using namespace std;
int t,n;
bool move1,move2,book1[1001][1001],book2[1001][1001];
int w[5][2]={{0,1},{1,0},{0,-1},{-1,0}};
struct node{int x1,y1,d1,x2,y2,d2;};
bool check1(node f)
{
f.x1+=w[f.d1][0];
f.y1+=w[f.d1][1];
if(f.x1>=n || f.x1<0 || f.y1>=n || f.y1<0 || book1[f.x1][f.y1]==true)
return true;
return false;
}
bool check2(node f)
{
f.x2+=w[f.d2][0];
f.y2+=w[f.d2][1];
if(f.x2>=n || f.x2<0 || f.y2>=n || f.y2<0 || book2[f.x2][f.y2]==true)
return true;
return false;
}
int main()
{
freopen("fight.in","r",stdin);
freopen("fight.out","w",stdout);
scanf("%d",&t);
for(int i=1;i<=t;++i)
{
memset(book1,false,sizeof(book1));
memset(book2,false,sizeof(book2));
move1=move2=false;
queue<node > q;
node f,p;
scanf("%d",&n);
scanf("%d%d%d%d%d%d",&f.x1,&f.y1,&f.d1,&f.x2,&f.y2,&f.d2);
q.push(f);
while(!q.empty())
{
f=q.front();
q.pop();
if(move1 && move2)//如果两人都不能走，说明永远不会相遇
{
printf("-1
");
break;
}
book1[f.x1][f.y1]=true;
book2[f.x2][f.y2]=true;//记录
if(f.x1==f.x2 && f.y1==f.y2)
{
printf("%d %d
",f.x1,f.y1);
break;
}
if(!move1 && book1[f.x1+w[f.d1][0]][f.y1+w[f.d1][1]]==true ||
f.x1+w[f.d1][0]<0 || f.x1+w[f.d1][0]>=n || f.y1+w[f.d1][1]<0 || f.y1+w[f.d1][1]>=n)
{
f.d1+=1;
f.d1%=4;
if(check1(f))//一定要在d值改变的后面
move1=true;
}
if(!move2 && book2[f.x2+w[f.d2][0]][f.y2+w[f.d2][1]]==true ||
f.x2+w[f.d2][0]<0 || f.x2+w[f.d2][0]>=n || f.y2+w[f.d2][1]<0 || f.y2+w[f.d2][1]>=n)
{
f.d2-=1;
if(f.d2==-1)
f.d2=3;
if(check2(f))
move2=true;
}
if(!move1)
{
p.x1=f.x1+w[f.d1][0];
p.y1=f.y1+w[f.d1][1];
}
else
{
p.x1=f.x1;
p.y1=f.y1;
}
if(!move2)
{
p.x2=f.x2+w[f.d2][0];
p.y2=f.y2+w[f.d2][1];
}
else
{
p.x2=f.x2;
p.y2=f.y2;
}
p.d1=f.d1;
p.d2=f.d2;
q.push(p);
}
}
}