93分第3个点WA, 广搜求助

P2895 [USACO08FEB] Meteor Shower S

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

原因: 数据中存在零时坠落的流星。


|