玛德 我现在特别想骂人 这道题真特么的坑爹 坑爹 坑爹 航电你就不能吧数据搞的好一点么 写了我几乎整整一天

我也不想多说什么了 真的 让我静静 这时间浪费的太不值了…………

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
using namespace std;

char g[220][220];
int sx,sy,ex,ey;
int row,col,keynum;
bool flag[202][202][1<<7][4];
int mve[][2] = {{-1,0},{0,-1},{1,0},{0,1}};
struct node
{
    int key,num;
    int x,y;
    node(){}
    node(int _x,int _y,int change=0,int status=0):x(_x),y(_y),key(status),num(change) {}
};
int bfs()
{
    queue<node> que;
    node tmp,now;
    que.push(node(sx,sy));
    memset(flag,false,sizeof(flag));
    while(!que.empty())
    {
        tmp = que.front();
        que.pop();
        for(int i = 0; i < 4; i++)
        {
            int x = tmp.x;
            int y = tmp.y;
            int ss = tmp.key;
            int dir=i;
            while(1)
            {
                if(g[x][y] =='L') dir=1;
                if(g[x][y] == 'U') dir=0;
                if(g[x][y] == 'D') dir=2;
                if(g[x][y] == 'R') dir=3;
                if(flag[x][y][ss][dir])break;
                flag[x][y][ss][dir] = true;
                if(g[x][y]>='0'&&g[x][y]<'8')
                 ss |= (1<<(g[x][y]-'0'));
                if( x == ex && y== ey && ss ==keynum)
                    return tmp.num+1;
                if(x+mve[dir][0]>=0 && x+mve[dir][0]<row&& y+mve[dir][1]>=0 && y+mve[dir][1]<col)
                    if( g[x+mve[dir][0]][y+mve[dir][1]]=='#' )
                    {
                        que.push(node(x,y,tmp.num+1,ss));
                        break;
                    }
                    else
                    {
                        x+=mve[dir][0];
                        y+=mve[dir][1];
                    }
                else  break;
            }
        }
    }
    return -1;
}

int main()
{
    while(scanf("%d%d",&row,&col)!=EOF)
    {
        keynum = 0;
        for(int i = 0; i < row; i++)
        {
            scanf("%s",g[i]);
            for(int j = 0; j < col; j++)
                if(g[i][j] == 'S')
                    sx = i,sy = j;
                else if(g[i][j] == 'E')
                    ex = i,ey = j;
                else if(g[i][j] == 'K')
                    g[i][j]='0'+keynum++;
        }
        keynum=(1<<keynum)-1;
        printf("%d\n",bfs());
    }
    return 0;
}
Categories: BFS

发表评论

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

Related Posts

BFS

CodeForces 295C Greg and Friends

bfs + dp 好题。 真好,比赛的时候想不出来,看题解的时候感觉好 Read more…

BFS

HDU 1043 Eight

康复计划之搜索 1 因为有个小学弟在第二天就说ida * 看不懂,搞得 Read more…

BFS

UVa 11624 基础BFS

白书训练指南上的第一道基础题,因为它在搜索中引入了超级源点,所以我自己 Read more…