做题感悟：这题一看就知道要用状态压缩，本题和HDU 1429 胜利大逃亡（续）差不多。
解题思路：你可以把宝物压缩为二进制，例如：01001 代表你已经拿过 1 号和 4 号宝物了 0 代表相应的宝物没拿。用同样的方法把拿某个物品的前提条件也映射成二进制。假如你现在遇到 3 号宝物，如果3号宝物的前提条件是拿到 1 号 和 4 号宝物才能拿 3 号，那么前提条件可以用二进制表示为 ：01001 那么只要将这个二进制与你当前的 key 相与如果结果还是等于前提条件的二进制，表示前提条件已经满足。so 3 号物品可以取走（前提是没取过三号物品），否则不可以。
代码：
#include<stdio.h>
#include<iostream>
#include<map>
#include<stack>
#include<string>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std ;
#define LEN sizeof(struct node)
#define lld long long int
const double PI = 3.1415926 ;
const double INF = 99999999 ;
const int MX =25 ;
int n,m,mx ;
char s[MX][MX] ;
int b[MX] ;
int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1} ;
bool vis[MX][MX][MX] ;// 标记数组
struct node
{
int x,y,key,step ;
} ;
bool search(int x,int y) // 判断是否出界
{
if(x<0||y<0||x>=n||y>=m||s[x][y]=='#')
return false ;
return true ;
}
int bfs(int x,int y)
{
int key,sx,sy,temp ;
memset(vis,false,sizeof(vis)) ;
queue<node>q ;
node curt,next ;
curt.x=x ;
curt.y=y ;
curt.key=0 ;
curt.step=0 ;
vis[x][y][0]=true ;
q.push(curt) ;
while(!q.empty())
{
curt=q.front() ;
q.pop() ;
if(curt.key==(1<<mx)-1&&s[curt.x][curt.y]=='E')
return curt.step ;
for(int i=0 ;i<4 ;i++)
{
next.x=sx=curt.x+dx[i] ;
next.y=sy=curt.y+dy[i] ;
next.step=curt.step+1 ;
next.key=key=curt.key ;
if(search(sx,sy)) // 判断是否出界
{
if(s[sx][sy]>='0'&&s[sx][sy]<='9') // 是宝藏
{
temp=s[sx][sy]-'0' ;
if(key&(1<<temp)) // 已经取过
{
if(!vis[sx][sy][key])
{
vis[sx][sy][key]=true ;
next.key=key ;
q.push(next) ;
}
}
else // 还没取过
{
temp=s[sx][sy]-'0' ;
if((key&b[temp])==b[temp])// 取该宝物的前提条件已经满足
{
next.key=key|(1<<temp) ;
vis[sx][sy][next.key]=true ;
q.push(next) ;
}
else if(!vis[sx][sy][key])// 前提条件没满足
{
vis[sx][sy][key]=true ;
next.key=key ;
q.push(next) ;
}
}
}
else if(!vis[sx][sy][key])// 不是宝藏
{
next.key=key ;
vis[sx][sy][key]=true ;
q.push(next) ;
}
}
}
}
return -1 ;
}
int main()
{
int sx,sy ;
while(~scanf("%d%d",&n,&m))
{
for(int i=0 ;i<n ;i++)
{
scanf("%s",s[i]) ;
for(int j=0 ;j<m ;j++)
if(s[i][j]=='S')
{
sx=i ;
sy=j ;
}
else if(s[i][j]>='0'&&s[i][j]<='9')
mx++ ;
}
int nx,ans=0,y ;
for(int i=0 ;i<mx ;i++)
{
scanf("%d",&nx) ;
ans=0 ;
for(int j=0 ;j<nx ;j++)
{
scanf("%d",&y) ;
ans=ans|(1<<y) ;
}
b[i]=ans ;// 取第 i 个宝物的前提条件
}
int an=bfs(sx,sy) ;
if(an!=-1)
printf("%d\n",an) ;
else printf("Impossible\n") ;
}
return 0 ;
}