玛德 我现在特别想骂人 这道题真特么的坑爹 坑爹 坑爹 航电你就不能吧数据搞的好一点么 写了我几乎整整一天
我也不想多说什么了 真的 让我静静 这时间浪费的太不值了…………
#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;
}