这是一道交互题

题意:你被丢进了一个30*30的箱子里

每一次你能上下左右瞎走

走到某个地方,也许你会撞墙[BLOCKED],或者能过的去[EMPTY]

求遍历所有你能走的格子

第一次做交互题,思考了下

dfs到一个未知区域...就行了...试探一下

如此往复直到所有区域都已知,输出DONE结束程序即可

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<string>
#include<math.h>
#include<time.h>
#include<vector>
#include<bitset>
#include<memory>
#include<utility>
#include<fstream>
#include<stdio.h>
#include<sstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
using namespace std;
int a[65][65];
bool visit[65][65];
bool last_ans=0;
int b[65][65]=
{
{1,1,1,1,1},
{1,0,0,0,1},
{1,1,0,0,1},
{1,1,1,1,1}};
int x=31,y=31;
char way[15][25]=
{"NORTH",
"SOUTH",
"EAST",
"WEST"};
void get_input()
{
    static char b[55];
    scanf("%s",b);
    last_ans=0;
    if (b[0]=='B') last_ans=1;
}
int dire[65][65];
bool dfs(int x,int y)
{
    if (a[x][y]==-1)
    {
        return 1;
    }
    if (visit[x][y]) return 0;
    //printf("Visited %d %d\n",x,y);
    visit[x][y]=true;
    if (a[x-1][y]!=1)
    {
        if (dfs(x-1,y))
        {
            dire[x][y]=1;
            return 1;
        }
    }
    if (a[x+1][y]!=1)
    {
        if (dfs(x+1,y))
        {
            dire[x][y]=0;
            return 1;
        }
    }
    if (a[x][y-1]!=1)
    {
        if (dfs(x,y-1))
        {
            dire[x][y]=3;
            return 1;
        }
    }
    if (a[x][y+1]!=1)
    {
        if (dfs(x,y+1))
        {
            dire[x][y]=2;
            return 1;
        }
    }
    return 0;
}
int main()
{
    #ifdef absi2011
    #endif
    memset(a,-1,sizeof(a));
    a[x][y]=0;
    for (;;)
    {
        memset(visit,false,sizeof(visit));
        if (dfs(x,y)==0)
        {
            puts("DONE");
            return 0;
        }
        for (;;)
        {
            if (a[x][y]==-1)
            {
                a[x][y]=last_ans;
                break;
            }
            printf("%s\n",way[dire[x][y]]);
            fflush(stdout);
            get_input();
            int nowx=x,nowy=y;
            if (dire[x][y]==0)
            {
                x++;
            }
            else if (dire[x][y]==1)
            {
                x--;
            }
            else if (dire[x][y]==2)
            {
                y++;
            }
            else
            {
                y--;
            }
            if (last_ans==1)
            {
                a[x][y]=1;
                //printf("%d %d\n",x,y);
                x=nowx;
                y=nowy;
                break;
            }
        }
    }
    return 0;
}