程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> scu oj 4445 Right turn 2015年四川省賽J題（模擬題）

scu oj 4445 Right turn 2015年四川省賽J題（模擬題）

編輯：關於C++

一般的模擬題。對於出現過的每一個x建立一個set 集合，對於y也如此。然後查找要走到哪個點即可，主要要對狀態記錄，判斷是否無線循環，否者出現無線循環的情況，就tle了。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int mmax = 500010;
const int inf=0x3fffffff;
struct node
{
    int x,y;
    void read()
    {
        scanf("%d %d",&x,&y);
    }
    node(int x,int y):x(x),y(y) {}
    node() {}
    bool operator < (const node &a) const
    {
        if(x==a.x)
            return yqx,qy;
set Sx[2100],Sy[2100];
int dir[4][2]={1,0,0,-1,-1,0,0,1};
mapq;
bool vis[10100][4];
bool fuck(int x,int y)
{
    int cnt=0;
    for(int i=0;i<4;i++)
    {
        int tx=x+dir[i][0];
        int ty=y+dir[i][1];
//        if(x==0 && y==0)
//        {
//            cout<::iterator it;
                if(fuck(nowx,nowy))
                {
                    fg=0;
                    break;
                }
                it=Sy[ qy[nowy] ].upper_bound(nowx);
                if(it!=Sy[ qy[nowy] ].end())
                {
                    int tx=*it;
                    tx--;
                    nowx=tx;
                    nowdir++;
                    nowdir%=4;
                    cnt++;
                }
                else
                    break;
            }
            else if(nowdir==1)
            {
                if(!qx.count(nowx))
                    break;
                set::iterator it;
                if(fuck(nowx,nowy))
                {
                    fg=0;
                    break;
                }
                it=Sx[ qx[nowx] ].lower_bound(nowy);
                if(it!=Sx[ qx[nowx] ].begin())
                {
                    it--;
                    int ty=*it;
                    ty++;
                    nowy=ty;
                    nowdir++;
                    nowdir%=4;
                    cnt++;
                }
                else
                    break;
            }
            else if(nowdir==2)
            {
                if(!qy.count(nowy))
                    break;
                set::iterator it;
                if(fuck(nowx,nowy))
                {
                    fg=0;
                    break;
                }
                it=Sy[ qy[nowy] ].lower_bound(nowx);
                if(it!=Sy[ qy[nowy] ].begin())
                {
                    it--;
                    int tx=*it;
                    tx++;
                    nowx=tx;
                    nowdir++;
                    nowdir%=4;
                    cnt++;
                }
                else
                    break;

            }
            else if(nowdir==3)
            {
                if(!qx.count(nowx))
                    break;
                set::iterator it;
                if(fuck(nowx,nowy))
                {
                    fg=0;
                    break;
                }
                it=Sx[ qx[nowx] ].upper_bound(nowy);
                if(it!=Sx[ qx[nowx] ].end())
                {
                    int ty=*it;
                    ty--;
                    nowy=ty;
                    nowdir++;
                    nowdir%=4;
                    cnt++;
                }
                else
                    break;
            }
        }
        if(!fg)
            puts("-1");
        else
            printf("%d\n",cnt);

    }
    return 0;
}