hdu2128之BFS (二)
int dir[4][2]={0,1,0,-1,1,0,-1,0};
struct Node{
int x,y,num,time;
unsigned long long open;//表示已经炸过的墙(最多8*8位)
unsigned long long key;//表示已经取过的炸药位置(最多8*8)
Node(){}
Node(int X,int Y,int Num,int Time,unsigned long long Open,unsigned long long Key){
x=X,y=Y,num=Num;
time=Time,open=Open,key=Key;
}
bool operator<(Node const &a)const{
return time>a.time;
}
}start;
bool check(Node &next){
int size=mark[next.x][next.y][next.num].size();
for(int i=0;iq;
Node oq,next;
q.push(start);
while(!q.empty()){
oq=q.top();
q.pop();
for(int i=0;i<4;++i){
next=Node(oq.x+dir[i][0],oq.y+dir[i][1],oq.num,oq.time+1,oq.open,oq.key);
if(next.x<0 || next.y<0 || next.x>=n || next.y>=m)continue;
if(Map[next.x][next.y] == 'X'){//该点是墙
int k=next.x*m+next.y;
if( !((next.open>
>k)&1) )--next.num,++next.time;//是否已炸过
next.open|=((1ll)<='1' && Map[next.x][next.y]<='9'){//该点有炸药可取
int k=next.x*m+next.y;
if( !((next.key>>k)&1) )next.num+=Map[next.x][next.y]-'0';//是否已取过
next.key|=((1ll)<>n>>m,n+m){
Init();
memset(mark,-1,sizeof mark);
for(int i=0;i>Map[i];
for(int i=0;i