jimbfs与dfs解题研究报告

《jimbfs与dfs解题研究报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、个人收集整理仅供参考学习BFS与DFS解题报告报告人：李锦一、题目简介：1002Hdu19831003Hdu14281004Hdu2918第一题难度较大，暂时不用考虑去做小结：二、题目分析与源码10021.题目描述：ProblemDescription破解字迷之后，你得知Kid将会在展览开始后T分钟内盗取至少一颗宝石，并离开展馆.整个展馆呈矩形分布，划分为NM个区域，有唯一地入口和出口（不能从出口进入，同样不能从入口出去）.由某个区域可直接移动至相邻四个区域中地一个，且最快需要一分钟.假设Kid进入放有宝石地区域即可盗取宝石，无需耗时.问至少要封

2、锁几个区域（可以封锁放有宝石地区域，但不能封锁入口和出口）才能保证Kid无法完成任务.b5E2RGbCAPInput输入地第一行有一个整数C，代表有C组测试数据.每组测试数据地第一行有三个整数N，M，T(2<=N,M<=8,T>0).接下来N行M列为展馆布置图，其中包括：'S'：入口'E'：出口'J'：放有宝石地区域，至少出现一次'.'：空白区域'#'：墙p1EanqFDPwOutput对每组测试数据，输出至少要封锁地区域数.SampleInput2555SJJJJ..##J.JJJJ19/19个人收集整理仅供参考学习.J...EJ...556S

3、JJJJ..##J.JJJJ.J...EJ...SampleOutput1.思路分析：封锁出口或者入口周围地格子.最多需要4个封锁点.所以我们可以采取这样地策略:1.寻找一条盗贼地可行路线,如果没有,返回0.2.计算封锁出口和入口四周需要地封锁点数量,取小地一个,假设是k,k<=43.从少到多,遍历所有封锁点个数小于k地方案,验证是否是一条有效地覆盖方案(可以通过是否阻止了1中地盗贼线路进行快速验证).如果有有效覆盖方案,返回这个方案地覆盖点值,否则继续.4.如果没有比k小地覆盖方案,返回k.时间复杂度:最多(MN)^3次有效覆盖验证.即(88)

4、^3=256k次.其中有很大一部分可以通过快速验证排除(取决于1地路径长短,所以一般1应该求出最短路径地可行路线)DXDiTa9E3d2.C++代码#include#include#includeusingnamespacestd;intn,m,t,ans;intdir[4][2]={1,0,-1,0,0,-1,0,1};charmap[10][10];boolvis[2][10][10];structnode{intx,y,t,k;introx[64],roy[64];};nodestart,e

5、nd,temp,in;queueQ;voiddfs(intdeep)19/19个人收集整理仅供参考学习{if(deep>ans)return;inti,j,minstep=-1;nodeq;while(!Q.empty())//清空队列Q.pop();Q.push(start);//起始位置入队memset(vis,false,sizeof(vis));//初始化标记数组vis[0][start.x][start.y]=true;//标记起始点为真while(!Q.empty())//从起点开始寻找一条路径{q=Q.front();Q

6、.pop();if(q.t>t)continue;if(q.k&&map[q.x][q.y]=='E')//找到出口{minstep=q.t;break;}for(i=0;i<4;i++)//分别从四个方向开始扫描{intxx=q.x+dir[i][0];intyy=q.y+dir[i][1];if(xx<0xx>=nyy<0yy>=mmap[xx][yy]=='#')RTCrpUDGiTcontinue;//越界或碰到墙if(map[xx][yy]=='J')in.k=1;//碰到珠宝elsein.k=q.k;//没有碰到则标记为前一个状态if

7、(!vis[in.k][xx][yy]){vis[in.k][xx][yy]=true;for(j=1;j<=q.t;j++){in.rox[j]=q.rox[j];in.roy[j]=q.roy[j];}in.x=xx;in.y=yy;in.t=q.t+1;in.rox[in.t]=xx;in.roy[in.t]=yy;Q.push(in);19/19个人收集整理仅供参考学习}}}if(minstep==-1){//minstep==-1表明在t时间内即使不用设置关卡也不能成功逃离if(deep

8、rcc;for(i=1;i