hdu 1429 bfs+狀態壓縮
//開一個三維標記數組，標記Ignatius有沒有以拿到鑰匙的狀態到達該位置
//由於鑰匙的個數最多十個，所以可以用狀態壓縮來做
//用1和0表示有沒有第i種鑰匙，這樣對於這個人拿到的鑰匙狀態就可以用二進制數表示
//用bfs找到最小值
#include
#include
#include
#include
using namespace std ;
const int maxn = 30;
const int inf = 0x7fffffff;
int vis[maxn][maxn][1<<10];
char map[maxn][maxn] ;
int ans = ans;
struct node
{
int x , y;
int step ;
int state ;
};
int st_x , st_y ;
int n , m;
int dx[4] = {-1,0,1,0} ;
int dy[4] = {0,1,0,-1} ;
queue que;
void bfs()
{
while(que.size())
que.pop() ;
memset(vis, 0 ,sizeof(vis)) ;
struct node first = {st_x , st_y , 0 ,0} ;
vis[st_x][st_y][0] = 1;
que.push(first) ;
while(que.size())
{
struct node now = que.front() ;
que.pop() ;
if(map[now.x][now.y] == '^')
{
ans = now.step ;
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 > m)
continue ;
if(map[next.x][next.y] >= 'A' && map[next.x][next.y] <= 'J')
if(!(now.state & (1<<(map[next.x][next.y] - 'A'))))
continue ;
if(map[next.x][next.y] >= 'a' && map[next.x][next.y] <= 'j')
{
next.state = now.state | (1<<(map[next.x][next.y]-'a')) ;
next.step = now.step + 1;
if(vis[next.x][next.y][next.state])
continue ;
que.push(next) ;
vis[next.x][next.y][next.state] = 1;
continue;
}
next.state = now.state ;
next.step = now.step + 1;
if(vis[next.x][next.y][next.state])
continue ;
vis[next.x][next.y][next.state] = 1;
que.push(next) ;
}
}
}
int main()
{
// freopen(in.txt,r,stdin) ;
int time ;
while(scanf(%d%d%d, &n , &m , &time) != EOF)
{
for(int i = 1;i <= n;i++)
{
scanf(%s , &map[i][1]);
for(int j = 1;j <= m;j++)
if(map[i][j] == '@')
st_x = i,st_y = j;
}
ans = inf ; //可能到不了終點，所以有可能bfs沒有更新ans
bfs(); //所以ans每次都要初始化
if(ans < time)
printf(%d , ans);
else
printf(-1 );
}
return 0;
}
