HDU 2128 Tempter of the Bone II(BFS)

转载请注明出处，谢谢 http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=2128

这题出现在BFS专题里，是yobobobo提出做的，我便看了看，中途也和yobobobo讨论了许多，得到一些启发

这题网上好多的BFS代码都是错的，HDOJ的数据比较弱

题目意思不难理解，取一些，炸开一些墙以最快的速度找到出口。由于有最短时间的问题，首选就是BFS了，其实后来想想也许用DFS早就解决了。

如果用BFS的话状态表示以及判重会有很大问题，一开始觉得flag[x][y][bomb]判重就够了，其实不然，相同的bomb数量其实状态是不一样的，

后来想到由于会炸掉一些墙，会取走一些，就得传递整个图。一下子在结点里放放入两个二维数组，想了想地图不是很大，应该不 会MLE，

那么在flag[x][y][bomb]每个状态取最小的步数的情况，最终必然是WA了，因为步数越小不一定是最佳，还要牵扯整个图的情况。于是想到用整

张图来判重，vector<Node>flag[x][y][bomb]来判重，结点里还有二维数组，YY了半天之后，提交果断是MLE，之前在和yobobobo讨论的时候

便想到了二进制压缩状态保存整个图，因为8*8刚好64位整数可以保存，而且不论是墙还是个数都少于64，果断改成二进制压缩，注意一些细节之后

测了许多数据没问题提交还是WA，不过果断发现是位运算溢出了，囧，再提交还是WA，一下子陷入悲剧当中。不断修改，各种错误都出来了，MLE

WA,TLE，都是由于状态判重部分导致。最后仔细一看题，发现是0 0结束，我却一直只是判断EOF，囧死，终于AC。

艰难的一题啊，不过yobobobo的探索精神令人感动，加油啊！！！

代码里有注释，另外附上一组数据

6 5
S.XX1
X.1X1
XX.X.
XXXXX
XXXXX
XXXDX

答案是17并不是-1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define LL unsigned long long
using namespace std;
int n,m;
int way[4][2]={{0,1},{0,-1},{1,0},{-1,0}};   //BFS四个方向
char mmap[10][10];                           //原始地图
int wallcnt,wallmap[10][10];                 //原始地图上墙的数量，以及分布图，对于每个墙给个编号
int bombcnt,bombmap[10][10];                 //原始地图上的数量，以及分布图，对于每个给个编号
struct Node{
	int x,y,step,bomb;      //位置，步数，剩余
	LL vis;                 //地图上的已取情况，1表示某处已取
	LL wall;                //地图上剩余墙的情况，1表示某处还有墙
	bool check(){           //判断是否在地图范围内
		if(x>=0&&y>=0&&x<n&&y<m)
			return true;
		return false;
	}                       //优先队列
	bool operator<(const Node n1) const{
		return step>n1.step;
	}
}s,e,u,v;                   
vector<Node>flag[8][8][8*8*9+1];   //判重，flag[x][y][z]表示 在(x,y)处手上有z个时的状态
bool check(Node tmp){              //判断是否和之前已入队的情况相同
	for(int i=0;i<flag[tmp.x][tmp.y][tmp.bomb].size();i++)
		if(tmp.wall==flag[tmp.x][tmp.y][tmp.bomb][i].wall&&tmp.vis==flag[tmp.x][tmp.y][tmp.bomb][i].vis)    //结点剩余的墙情况以及情况完全相同
			return false;
	return true;
}
int bfs(){
	priority_queue<Node>que;
	que.push(s);
	while(!que.empty()){
		u=que.top();
		que.pop();
		for(int i=0;i<4;i++){
			v=u;
			v.step++;
			v.x=u.x+way[i][0];
			v.y=u.y+way[i][1];
			if(v.check()){
				if(mmap[v.x][v.y]=='D')          //找到终点
					return v.step;
				if(mmap[v.x][v.y]=='X'&&((1LL<<wallmap[v.x][v.y])&v.wall)){    //某处原来是墙，而且也没被炸毁
					if(v.bomb>0){    //手上有
						v.bomb--;
						v.step++;
						v.wall^=(1LL<<wallmap[v.x][v.y]);    //标记下，已经被炸毁
						que.push(v);                           //结点入队
						flag[v.x][v.y][v.bomb].push_back(v);   //保存状态
					}	
				}  
				else if(mmap[v.x][v.y]>='1'&&mmap[v.x][v.y]<='9'&&(v.vis&(1LL<<bombmap[v.x][v.y]))==0){    //某处是，而且之前没有取
					v.bomb+=mmap[v.x][v.y]-'0';             //取
					v.vis|=(1LL<<bombmap[v.x][v.y]);         //标记已取
					que.push(v);                              //结点入队
					flag[v.x][v.y][v.bomb].push_back(v);       //保存状态
				}
				else{
					if(flag[v.x][v.y][v.bomb].empty()||check(v)){   //当前没有状态或者和之前的状态都不相同
						flag[v.x][v.y][v.bomb].push_back(v);      //保存
						que.push(v);         //入队
					}
				}        
			}

		}
	}
	return -1;
}
int main(){
	while(scanf("%d%d",&n,&m)!=EOF&&n+m){ 
		for(int i=0;i<n;i++)           //判重初始化
			for(int j=0;j<m;j++)
				for(int k=0;k<=(n*m*9);k++)
					if(!flag[i][j][k].empty())
						flag[i][j][k].clear();
		bombcnt=wallcnt=0;
		memset(wallmap,-1,sizeof(wallmap));
		memset(bombmap,-1,sizeof(bombmap));
		for(int i=0;i<n;i++){
			scanf("%s",mmap[i]);
			for(int j=0;j<m;j++)
				if(mmap[i][j]=='S'){            //起点标记
					s.x=i;
					s.y=j;
					s.step=0;
					s.bomb=0;
					s.vis=0;
				} 
				else if(mmap[i][j]=='X')           
					wallmap[i][j]=wallcnt++;             //对于每个墙给个编号
				else if(mmap[i][j]>='1'&&mmap[i][j]<='9')
					bombmap[i][j]=bombcnt++;           //对于每个位置给个编号
		}
		s.wall=(1LL<<wallcnt)-1;               //初始化，所有墙都没有被炸
		printf("%d\n",bfs());
	}
	return 0;
}