题目概述贝茜从坐标原点 (0,0) 开始出发只能在横纵坐标非负的区域移动。每颗流星会在特定时刻砸向某个坐标同时摧毁该点和它上下左右四个相邻格子。被流星在时刻 t 摧毁的格子贝茜只能在 t 之前到达t 及之后不能踏足。走到永远不会被流星击中的格子即为安全点输出到达安全点耗费的最少时间若无路可走则输出 - 1。其实还有死路一条思路分析先预处理每个格子被流星摧毁的最早时刻一个格子若始终不会被砸则记为无穷大作为目标安全点。采用 BFS 进行广度优先搜索BFS 可以保证第一次搜到安全点时就是最短时间。移动时要保证到达格子的时间严格小于该格子被摧毁的时间队列遍历完没找到安全点就返回 - 1。AC代码#includebits/stdc.husingnamespacestd;intm,d[350][350];intdx[5]{0,1,-1,0,0};intdy[5]{0,0,0,1,-1};structnode{intx,y,t;};boolvis[350][350];intbfs(){if(d[0][0]0)return-1;queuenodeq;q.push({0,0,0});vis[0][0]true;while(!q.empty()){node curq.front();q.pop();if(d[cur.x][cur.y]0x3f3f3f3f)returncur.t;for(intk0;k5;k){intnxcur.xdx[k];intnycur.ydy[k];if(nx0nx350ny0ny350!vis[nx][ny]){intntcur.t1;if(d[nx][ny]nt){vis[nx][ny]true;q.push({nx,ny,nt});}}}}return-1;}intmain(){cinm;memset(d,0x3f,sizeof(d));for(inti0;im;i){intx_1,y_1,t_1;cinx_1y_1t_1;for(intk0;k5;k){intnxx_1dx[k];intnyy_1dy[k];if(nx0nx350ny0ny350){if(t_1d[nx][ny])d[nx][ny]t_1;}}}coutbfs();return0;}