Codeforces Beta Round 8 B Obsession with Robots

题目

源地址:

http://codeforces.com/problemset/problem/8/B

理解

在那遥远的地方有位好姑娘 ,人们走过她的帐篷都要留恋的张望 23333,不逗比了,真正的题解开始。 在一个无穷大的平面上,有一个机器人可以自由地上下左右移动。然后在它移动的路径上,你可以给它设置任意个障碍。如果存在一种障碍的设计,使得机器人的移动路径是最短路径,则OK;如果不存在,则存在BUG。 这道题写得很逗= =。一开始作死用switch来写,不过在字符的判断上好像写搓了,怎么写都是BUG。后来想到可以用一个vis来标记机器人走过的路径,如果存在一个点被访问过两次,那么这个路径一定不是最短路径。不过这份代码挂了,原因是还存在另外一种可能,比如:URD。也就是说,只要形成一个类似于U的结构,也一定不是最短路径。一时半会儿没想出来什么高效的方案,干脆暴力敲了一个。设一个flag出来,然后每走一个点,就四个方向判断一下是否访问过,如果flag>=2,说明一定是BUG。 多亏了CF机子好,居然过了,也是RP好。

代码


#define MAXN 100+10

char road[MAXN];
int vis[2*MAXN][2*MAXN];
int x=105,y=105,len;

bool solve()
{
    for(int i=0; i<len; i++)
    {
        if(road[i]=='L')
        {
            x-=1;
            if(vis[x][y]==1)    return false;
            int flag=0;
            if(vis[x-1][y]) flag++;
            if(vis[x+1][y]) flag++;
            if(vis[x][y+1]) flag++;
            if(vis[x][y-1]) flag++;
            if(flag>=2) return false;
            vis[x][y]=1;
        }
        else if(road[i]=='U')
        {
            y+=1;
            if(vis[x][y]==1)    return false;
            int flag=0;
            if(vis[x-1][y]) flag++;
            if(vis[x+1][y]) flag++;
            if(vis[x][y+1]) flag++;
            if(vis[x][y-1]) flag++;
            if(flag>=2) return false;
            vis[x][y]=1;
        }
        else if(road[i]=='R')
        {
            x+=1;
            if(vis[x][y]==1)    return false;
            int flag=0;
            if(vis[x-1][y]) flag++;
            if(vis[x+1][y]) flag++;
            if(vis[x][y+1]) flag++;
            if(vis[x][y-1]) flag++;
            if(flag>=2) return false;
            vis[x][y]=1;
        }
        else
        {
            y-=1;
            if(vis[x][y]==1)    return false;
            int flag=0;
            if(vis[x-1][y]) flag++;
            if(vis[x+1][y]) flag++;
            if(vis[x][y+1]) flag++;
            if(vis[x][y-1]) flag++;
            if(flag>=2) return false;
            vis[x][y]=1;
        }
    }
    return true;
}

int main(int argc, char const *argv[])
{
    memset(vis,0,sizeof(vis));
    scanf("%s", road);
    len=strlen(road);
    vis[x][y]=1;
    if(solve()) printf("OK\n");
    else printf("BUG\n");
    return 0;
}

更新日志

  • 2014年11月16日 已AC。
comments powered by Disqus