题目

源地址：

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。