mushezi @ 2022-08-12 19:44:17
#include <bits/stdc++.h>
using namespace std;
int dx[] = {0, 0, 1, 0, -1};
int dy[] = {0, 1, 0, -1, 0}; // 为了读入方便就给 0, 0
int m;
int mp[305][305];
int x, y, t;
bool vis[305][305];
struct point{
int x, y, t;
} ;
queue<point> q;
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> m;
for(int i = 1; i <= m; i++){
cin >> x >> y >> t;
for(int j = 0; j < 5; j++){
if(x+dx[j]>=0 && x+dx[j]<=301 && y+dy[j]>=0 && y+dy[j]<=301 && ((!mp[x+dx[j]][y+dy[j]]) || t<mp[x+dx[j]][y+dy[j]])) mp[x+dx[j]][y+dy[j]] = t;
}
}
vis[0][0] = 1;
q.push({0, 0, 0});
while(!q.empty()){
auto p = q.front();
q.pop();
if(!mp[p.x][p.y]){
cout << p.t ;
return 0;
}
for(int i = 1; i < 5; i++){
int px = p.x + dx[i];
int py = p.y + dy[i];
if(px>=0 && px<=301 && py>=0 && py<=301 && !vis[px][py] && ((mp[px][py]&&p.t+1<mp[px][py]) || (!mp[px][py]))){
vis[px][py] = 1;
q.push({px, py, p.t+1});
}
}
}
cout << -1 ;
return 0;
}
如标题, 求助
by GFyyx @ 2022-08-12 21:01:02
用dfs不香吗?
by 鱼跃于渊 @ 2022-08-23 13:20:50
In:
5
0 0 2
3 0 0
1 2 5
2 2 4
1 4 4
Output:
3
Answer:
2
原因: 数据中存在零时坠落的流星。