转载请注明出处,谢谢 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;
}
分享到:
相关推荐
hdu 3085 一道bfs题 一点值得注意的,鬼魅先走,mm与gg后走,直接模拟这个这个场景,突出时间的先后性,一秒与一秒的区别。。。这样模拟很难出错
The least common multiple (LCM) of a set of positive integers is the smallest positive integer which is divisible by all the numbers in the set. For example, the LCM of 5, 7 and 15 is 105. Input Input...
The first line of the input contains an integer T(1≤T≤10), denoting the number of test cases. In each test case, there are two integers k,m(1≤k≤1018,1≤m≤100). Output For each test case, print ...
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
杭电ACMhdu1163
HDU1059的代码
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码
搜索 dfs 解题代码 hdu1241
hdu 5007 Post Robot 字符串枚举。 暴力一下就可以了。
hdu acm 教案 动态规划(1) hdu acm 教案 动态规划(1)
ACM HDU题目分类,我自己总结的大概只有十来个吧
hdu 1166线段树代码
HDU最全ac代码
hdu动态规划算法集锦
自己做的HDU ACM已经AC的题目
hdu题目分类