南京网站制作公司怎么样,怎么寻找要建设网站的客户群,深圳社保个人网页登录,重庆公司注册代理公司题目#xff1a;
Bessie听说有场史无前例的流星雨即将来临#xff1b;有谶言#xff1a;陨星将落#xff0c;徒留灰烬。为保生机#xff0c;她誓将找寻安全之所#xff08;永避星坠之地#xff09;。目前她正在平面坐标系的原点放牧#xff0c;打算在群星断其生路前转…题目
Bessie听说有场史无前例的流星雨即将来临有谶言陨星将落徒留灰烬。为保生机她誓将找寻安全之所永避星坠之地。目前她正在平面坐标系的原点放牧打算在群星断其生路前转移至安全地点。
此次共有M (1 ≤ M ≤ 50,000)颗流星来袭流星i将在时间点Ti (0 ≤ Ti ≤ 1,000) 袭击点 (Xi, Yi) (0 ≤ Xi ≤ 300; 0 ≤ Yi ≤ 300)。每颗流星都将摧毁落点及其相邻四点的区域。
Bessie在0时刻时处于原点且只能行于第一象限以平行与坐标轴每秒一个单位长度的速度奔走于未被毁坏的相邻通常为4点上。在某点被摧毁的刹那及其往后的时刻她都无法进入该点。
寻找Bessie到达安全地点所需的最短时间。
Input - 输入 * 第1行: 一个整数: M * 第2..M1行: 第i1行包含由空格分隔的三个整数: Xi, Yi, and Ti Output - 输出 * 仅一行: Bessie寻得安全点所花费的最短时间无解则为-1。
Sample Input - 输入样例 4 0 0 2 2 1 2 1 1 2 0 3 5 Sample Output - 输出样例 5
分析与解答
这里没有给出图而是通过一些数据让你先建一个图map[i][j]存的是这个点的爆炸时间我们初始化最大时间然后输入数据是把这个数以及他上下左右四个方位全部的时间填上这里可能会重复爆我们写最早爆的时间也就是最小的时间。 然后我们从00开始搜bfs中先把00放入队列然后只要队列不为空就继续搜先取出队首元素。由于如果某个点被炸掉他就不可能停在该点最终她停的点一定是没有被炸的那个点也就是说如果队首元素的map值是我们一开始赋的值maxn那我们就可以返回这个点的时间了。如果没返回就继续上下左右遍历更改点的坐标以及时间如果这个点没出现过而且他在第一象限而且此时此刻的时间小于map里开始爆的时间那就说明可以走这个点就把这个点push到队列里并做上标记
这个代码稍微改一点就wa一次时main里那个t不能写成map[i][j]还有一个是bfs里面参数的位置稍微一改就错具体错到哪我调试了两小时没调出来md以后干脆先建结点再判断吧参数再for里for外if里if外这东西我头疼 代码参考 https://blog.csdn.net/coraline_m/article/details/18035393
#includeiostream
#includecstdio
#includecstring
#includequeue
using namespace std;
int maxn10000;
int dir[4][2]{{-1,0},{1,0},{0,1},{0,-1}};
int mp[305][305];
int visi[305][305];
struct node
{int x,y,t;//坐标和时间
};int bfs(int x,int y)//从00点开始
{queuenode mq;node nod; nod.xx,nod.yy,nod.t0;mq.push(nod);while(!mq.empty()){int cx,cy,px,py,time;nodmq.front();mq.pop();cxnod.x,cynod.y,timenod.t;if(mp[cx][cy]maxn)//没有被炸掉 {//couttimeendl;return time;}for(int i0;i4;i)//00上下左右跑 {pxcxdir[i][0],pycydir[i][1];nod.xpx,nod.ypy,nod.ttime1;if(px0py0!visi[px][py]nod.tmp[px][py])//nod。t小于他说明可以走这个点 {visi[px][py]1;mq.push(nod);}}}return -1;
}int main()
{int n,i,j;int x,y,tim,cx,cy;while(cinn){for(i0;i304;i)for(j0;j304;j)mp[i][j]maxn;while(n--){scanf(%d%d%d,x,y,tim);mp[x][y]min(mp[x][y],tim);//mp存的是最早爆的时间 for(i0;i4;i)// 他上下左右四个点位全爆掉 {cxxdir[i][0],cyydir[i][1];if(cx0cy0) mp[cx][cy]min(mp[cx][cy],tim);//点在第一象限内 }}memset(visi,0,sizeof(visi));//初始化标志数组 visi[0][0]1;int resbfs(0,0);coutresendl;}return 0;
}
