温州网站推广驭明,厦门seo推广外包,什么软件制作图片,深圳微网站搭建[P2895 USACO08FEB] Meteor Shower S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
bfs。难点在于处理走到该点时的时间与该处陨石降落的时间的比较。
可以发现#xff0c;在某处可能有多个陨石降落#xff0c;但是此题只考虑陨石降落的最小时间。因此#xff0c;我们可…[P2895 USACO08FEB] Meteor Shower S - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
bfs。难点在于处理走到该点时的时间与该处陨石降落的时间的比较。
可以发现在某处可能有多个陨石降落但是此题只考虑陨石降落的最小时间。因此我们可以考虑根据陨石的降落位置和时间对陨石降落地进行预处理取最小时间。在此将二维空间初始化为 I N F INF INF因为题目保证了 T i ≤ 1000 T_i \le 1000 Ti≤1000因此等于 I N F INF INF的位置一定是没有陨石降落的。根据读入的陨石位置和时间预处理出该处陨石降落的最小时间。
之后进行bfs在搜到的位置 x , y x,y x,y处如果 p h x , y I N F ph_{x,y} INF phx,yINF表明该处一定没有陨石降落输出即可。否则需要判断该处合法没有超界没有访问过到此处的时间大于该处陨石降落的时间。 坑点可能还在于陨石降落是在 [ 0 , 300 ] [0, 300] [0,300]之间的但是人是可以走到300之外的位置的。 代码如下
namespace direction {
namespace d8 {
vectorint fx({0, 0, 1, 1, 1, -1, -1, -1}), fy({1, -1, 1, 0, -1, 1, 0, -1});
}
namespace d4 {
vectorint fx({0,0,1,-1}), fy({1,-1,0,0});
}
}
using namespace::direction::d4;void inpfile();
void solve() { int n; cinn;vectorvectorint ph(310, vectorint (310, INF));vectorvectorint vis(310, vectorint(310));for(int i 0; i n; i) {int x,y,t; cinxyt;// 预处理陨石位置附近的最小时间ph[x][y] min(ph[x][y], t);for(int j 0; j 4; j) {int xx x fx[j], yy y fy[j];// 只用考虑小于0的情况大于300的不用考虑。因为是陨石下降在[0, 300] 但是人是可以走到300之外的if(xx 0 || yy 0) continue;ph[xx][yy] min(ph[xx][yy], t);}}queuearrayint,3 q; // x, y, cnt;vis[0][0] 1;q.push({0, 0, 0});while(q.size()) {auto tmp q.front(); q.pop();int x tmp[0], y tmp[1], cnt tmp[2] 1;// 如果当前位置是INF表示没有陨石会降落输出返回即可if(ph[x][y] INF) {coutcnt - 1endl;return ;}// 否则该处会用陨石降落不是安全的地方for(int i 0; i 4; i) {int xx x fx[i], yy y fy[i];// 此时需要判断边界虽然人是可以超出300的但是显然303要比300003要优// 如果在此不进行判断则可能会死循环RECE等if(xx 0 || xx 303 || yy 0 || yy 303) continue;// 之前走过if(vis[xx][yy]) continue;// 走到此时该处就已经有陨石降落if(ph[xx][yy] cnt) continue;vis[xx][yy] 1;q.push({xx, yy, cnt}); }}cout-1endl;
}
