J. Right turn
Time Limit: 1000ms
Memory Limit: 65536KB
frog is trapped in a maze. The maze is infinitely large and divided into grids. It also consists of n obstacles, where the i-th obstacle lies in grid (xi,yi).
frog is initially in grid (0,0), heading grid (1,0). She moves according to The Law of Right Turn: she keeps moving forward, and turns right encountering a obstacle.
The maze is so large that frog has no chance to escape. Help her find out the number of turns she will make.
Input
The input consists of multiple tests. For each test:
The first line contains 1 integer n (0≤n≤103). Each of the following n lines contains 2 integers xi,yi. (|xi|,|yi|≤109,(xi,yi)≠(0,0), all (xi,yi) are distinct)
Output
For each test, write 1 integer which denotes the number of turns, or ‘‘-1′′ if she makes infinite turns.
Sample Input
2
1 0
0 -1
1
0 1
4
1 0
0 1
0 -1
-1 0
Sample Output
2
0
-1
暴力搜索,对于每个点最多有四次访问,就会有循环
#include <bits/stdc++.h>
#define LL long long
#define fread() freopen("in.in","r",stdin)
#define fwrite() freopen("out.out","w",stdout)
using namespace std;
const int INF = 0x3f3f3f3f;
typedef struct node
{
int x;
int y;
bool Dir[4];
} Node;
typedef struct Dirc//记录所在点的位置及其方向
{
int x;
int y;
int D;
} DI;
Node Pn[1010];
int n;
void init()
{
for(int i=1; i<=n; i++)
{
scanf("%d %d",&Pn[i].x,&Pn[i].y);
memset(Pn[i].Dir,false,sizeof(Pn[i].Dir));
}
}
int bfs()
{
queue<DI>Q;
DI a,b;
a.x=0;
a.y=0;
a.D=0;
Q.push(a);
int num=0;
while(!Q.empty())
{
b=Q.front();
Q.pop();
if(b.D==0||b.D==3)//(0:x轴正向,1:y轴负向 2:x轴负向 3:y轴正向)
{
int DD=INF;
int flag;
for(int i=1; i<=n; i++)
{
if(b.D==0)
{
if(Pn[i].y==b.y&&Pn[i].x>b.x)
{
if(DD>Pn[i].x)
{
DD=Pn[i].x;
flag=i;
}
}
}
else
{
if(Pn[i].x==b.x&&Pn[i].y>b.y)
{
if(DD>Pn[i].y)
{
DD=Pn[i].y;
flag=i;
}
}
}
}
if(DD==INF)
{
return num;
}
if(Pn[flag].Dir[b.D])
{
return -1;
}
else
{
Pn[flag].Dir[b.D]=true;
a.D=(b.D+1)%4;
if(b.D==0)
{
a.x=DD-1;
a.y=b.y;
}
else
{
a.x=b.x;
a.y=DD-1;
}
Q.push(a);
num++;
}
}
else if(b.D==2||b.D==1)
{
int DD = -INF;
int flag;
for(int i=1; i<=n; i++)
{
if(b.D==2)
{
if(Pn[i].y==b.y&&Pn[i].x<b.x)
{
if(DD<Pn[i].x)
{
DD=Pn[i].x;
flag=i;
}
}
}
else
{
if(Pn[i].x==b.x&&Pn[i].y<b.y)
{
if(DD<Pn[i].y)
{
DD=Pn[i].y;
flag=i;
}
}
}
}
if(DD==-INF)
{
return num;
}
if(Pn[flag].Dir[b.D])
{
return -1;
}
else
{
Pn[flag].Dir[b.D]=true;
a.D=(b.D+1)%4;
if(b.D==2)
{
a.x=DD+1;
a.y=b.y;
}
else
{
a.x=b.x;
a.y=DD+1;
}
Q.push(a);
num++;
}
}
}
return -1;
}
int main()
{
while(~scanf("%d",&n))
{
init();
printf("%d\n",bfs());
}
return 0;
}