//开一个四维数组，前面两维表示在图中的位置
//后面两维表示到达该位置有多少个钥匙和经过的路线有多少条蛇
//由于时间和步数不同步，所以得用优先队列来做
//或者遍历所有情况得到最大值
//由于钥匙需要按照顺序找，所以能直接记录最后一个钥匙的大小
//而对于经过蛇不是特定的顺序，所以对于蛇的记录可以运用一个二进制数表示
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 110;
const int inf = 0x7fffffff ;
char map[maxn][maxn];
int vis[maxn][maxn][10][32];
int dx[4] = {-1 , 0 , 1 , 0};
int dy[4] = {0 , 1 , 0 , -1};
int st_x,st_y,en_x,en_y;
int snake[maxn][maxn] ;
int N , M;
//int ans ;
struct node
{
int x,y ;
int state ;
int step;
int key ;
};
int get_num(int a)
{
int ans_a = 0;
int temp_a = a;
while(temp_a){
ans_a += (temp_a%2);
temp_a/=2;
}
return ans_a;
}
struct cmp{
bool operator()(struct node &a,struct node &b){
return a.step+get_num(a.state) > b.step+get_num(b.state);
}
};
int flag = 0;
void bfs()
{
memset(vis,0,sizeof(vis));
priority_queue<struct node,vector<struct node>,cmp> que;
//queue<struct node>que;
struct node first = {st_x,st_y,0,0,0};
que.push(first);
vis[st_x][st_y][0][0] = 1;
while(que.size())
{
struct node now = que.top();
//struct node now = que.front();
que.pop();
if(now.key == M && now.x == en_x && now.y == en_y)
{
printf("%d\n",now.step+get_num(now.state));
//ans = min(ans,now.step+get_num(now.state));
flag = 1;
break;
}
for(int i = 0;i < 4;i++)
{
struct node next ;
next.x = now.x + dx[i];
next.y= now.y + dy[i];
if(map[next.x][next.y] == ‘#‘ || next.x<1 || next.x>N || next.y<1 || next.y > N)
continue ;
if(map[next.x][next.y] == ‘.‘ || map[next.x][next.y] == ‘K‘ || map[next.x][next.y] == ‘T‘)
{
next.key = now.key ;
next.state = now.state;
}
else if(map[next.x][next.y] == ‘S‘)
{
if(!((1<<snake[next.x][next.y])&(now.state)))
next.state = now.state | (1<<snake[next.x][next.y]);
else
next.state = now.state ;
next.key = now.key ;
}
else if(map[next.x][next.y] >= ‘1‘ && map[next.x][next.y] <= ‘9‘)
{
if(now.key + 1 == (map[next.x][next.y] - ‘0‘))
next.key = map[next.x][next.y] -‘0‘;
else
next.key = now.key ;
next.state = now.state ;
}
if(vis[next.x][next.y][next.key][next.state])
continue;
vis[next.x][next.y][next.key][next.state] = 1;
next.step = now.step + 1;
que.push(next);
}
}
}
int main()
{
//freopen("in.txt","r",stdin);
while(scanf("%d%d",&N,&M)&&(N||M))
{
int num_s = 0;
for(int i = 1;i <= N;i++)
{
scanf("%s",&map[i][1]);
for(int j = 1;j <= N;j++)
{
if(map[i][j] == ‘S‘)
snake[i][j] = num_s++;
if(map[i][j] == ‘K‘)
st_x = i , st_y = j;
if(map[i][j] == ‘T‘)
en_x = i , en_y = j;
}
}
// ans = inf ;
flag = 0 ;
bfs();
if(!flag)
printf("impossible\n");
//if(ans == inf)
// printf("impossible\n");
// else
// printf("%d\n",ans);
}
return 0;
}
hdu5025 Saving Tang Monk bfs+状态压缩
原文：http://blog.csdn.net/cq_pf/article/details/44657375
