Right turn SCU – 4445

作者: zqqian 分类: ACM 发布时间: 2017-05-04 19:56

 

Right turn

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 \((x_i, y_i)\).

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 \leq n \leq 10^3\)). Each of the following \(n\) lines contains \(2\) integers \(x_i, y_i\). (\(|x_i|, |y_i| \leq 10^9, (x_i, y_i) \neq (0, 0)\), all \((x_i, y_i)\) 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

这个题的障碍物数目只有10^3 所以可以使用暴力模拟来做,先用一个结构体存下所有的点坐标,然后从(0,0)点开始模拟,搜索该方向上符合要求的距离最近的点,ans

++,一直到搜索不到符合要求的坐标。输出ans

同时用一个二维数组存储遇到障碍物的信息,如果发现某个障碍物在相同方向上碰到了两次,就可以输出-1了。

#include<iostream>
#include<cstring>
using namespace std;
struct point
{
    int x;
    int y;
};
int main()
{
    ios::sync_with_stdio(false);
    int n;
    point a[10000];
    int visit[10000];
    point now;
    int dir;
    while(cin>>n)
    {
        int t;
        int vis[10000][4]= {0};
        memset(visit,0,sizeof(visit));
        now.x=0;
        now.y=0;
        dir=0;
        for(int i=0; i<n; i++)
        {
            cin>>a[i].x>>a[i].y;
        }
        int ans=0;

        while(1)
        {


            if(dir==0)
            {
                point tem;
                bool f=true;
                for(int i=0; i<n; i++)
                {
                    if(a[i].y==now.y&&a[i].x>now.x)
                    {
                        if(f)
                        {
                            t=i;
                            tem.x=a[i].x;
                            tem.y=a[i].y;
                            f=false;
                        }
                        else
                        {

                            if(a[i].x<tem.x)
                            {
                                tem.x=a[i].x;
                                t=i;
                            }
                        }
                    }
                }

                if(!f)
                {
                    if(vis[t][dir]==1)
                    {
                        ans=-1;
                        break;
                    }
                    ans++;
                    now.x=tem.x-1;
                    vis[t][dir]=1;
                    dir=1;

//cout<<now.x<<" "<<now.y<<endl;
                }
                else
                    break;



            }
            if(dir==1)
            {
                point tem;
                bool f=true;
                for(int i=0; i<n; i++)
                {
                    if(a[i].x==now.x&&a[i].y<now.y)
                    {
                        if(f)
                        {
                            t=i;
                            tem.x=a[i].x;
                            tem.y=a[i].y;
                            f=false;
                        }
                        else
                        {
                            // tem.y=tem.y<a[i].x?a[i].x:tem.x;
                            if(a[i].y>tem.y)
                            {
                                tem.y=a[i].y;
                                t=i;
                            }
                        }
                    }

                }
                if(!f)
                {
                    if(vis[t][dir]==1)
                    {
                        ans=-1;
                        break;
                    }
                    ans++;
                    now.y=tem.y+1;
                    vis[t][dir]=1;
                    dir=2;

                    //  cout<<now.x<<" "<<now.y<<endl;
                }
                else
                    break;



            }
            if(dir==2)
            {

                point tem;
                bool f=true;
                for(int i=0; i<n; i++)
                {
                    if(a[i].y==now.y&&a[i].x<now.x)
                    {
                        if(f)
                        {
                            t=i;
                            tem.x=a[i].x;
                            tem.y=a[i].y;
                            f=false;
                        }
                        else
                        {
                            //tem.x=tem.x<a[i].x?a[i].x:tem.x;
                            if(a[i].x>tem.x)
                            {
                                tem.x=a[i].x;
                                t=i;
                            }
                        }
                    }}
                    if(!f)
                    {
                        if(vis[t][dir]==1)
                        {
                            ans=-1;
                            break;
                        }
                        ans++;
                        now.x=tem.x+1;
                        vis[t][dir]=1;
                        dir=3;

                        //cout<<now.x<<" "<<now.y<<endl;
                    }
                    else
                        break;



                }
                if(dir==3)
                {
                    point tem;
                    bool f=true;
                    for(int i=0; i<n; i++)
                    {
                        if(a[i].x==now.x&&a[i].y>now.y)
                        {
                            if(f)
                            {
                                t=i;
                                tem.x=a[i].x;
                                tem.y=a[i].y;
                                f=false;
                            }
                            else
                            {
                                // tem.y=tem.y>a[i].x?a[i].x:tem.x;
                                if(a[i].y<tem.y)
                                {
                                    tem.y=a[i].y;
                                    t=i;
                                }
                            }
                        }
                    }

                    if(!f)
                    {
                        if(vis[t][dir]==1)
                        {
                            ans=-1;
                            break;
                        }
                        ans++;
                        now.y=tem.y-1;
                        vis[t][dir]=1;
                        dir=0;

//cout<<now.x<<" "<<now.y<<endl;
                    }
                    else
                        break;

                }


            }
            cout<<ans<<endl;
        }
        return 0;
    }

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注