7分！（悬赏关注一个）

P2895 [USACO08FEB] Meteor Shower S

Algorithm_ZRF @ 2024-01-30 18:25:32

2AC,其余全WA

#include <bits/stdc++.h>
using namespace std;
const int maxm = 50005,maxn = 305;
int dx[] = {1,-1,0,0},
    dy[] = {0,0,1,-1};
struct meteor{
    int x,y,t;
}met[maxm];
int farm[maxn][maxn];
struct ss{
    int x,y,t;
};
int m;
inline void Read(){
    cin >> m;
    for(int i = 1;i <= m;++i){
        cin >> met[i].x >> met[i].y >> met[i].t; 
    }
}

inline int bfs(int x,int y,int t){
    queue<ss> q;
    ss s;//初始值
    s.x = x;
    s.y = y;
    s.t = t;
    q.push(s);
    priority_queue<int,vector<int>,less<int>> p;
    for(int i = 1;i <= m;++i){
        p.push(met[i].t);
    }
    int maxt = p.top();
    while(q.empty()){
        ss now = q.front();
        q.pop();
        for(int i = 1;i <= m;++i){
            if(now.t == met[i].t){
                farm[met[i].x][met[i].y] = 1;
                farm[met[i].x+1][met[i].y] = 1;
                farm[met[i].x-1][met[i].y] = 1;
                farm[met[i].x][met[i].y+1] = 1;
                farm[met[i].x][met[i].y-1] = 1; 
            }
        }
        if(now.t == maxt && farm[now.x][now.y] == 1){
            break;
        }
        if(now.t == maxt && farm[now.x][now.y] == 1){
            return now.t;
        }
        for(int i = 0;i < 4;++i){
            int tx = now.x + dx[i],
                ty = now.y + dy[i],
                tt = now.t + 1;
            if(tx < 0 || ty < 0) continue;//判断越界
            if(farm[tx][ty] == 1)continue;//判断此地是否有陨石砸过
            if(farm[tx][ty] == 2)continue;//判断此地是否已经走过
            farm[tx][ty] = 2; 
            q.push({tx,ty,tt}); 
        }
    } 
    return -1;
}

inline void solve(){
    Read();
    cout << bfs(0,0,0);
}

signed main(){
    solve();
    exit(0);
}

by xu_zhihao @ 2024-01-30 18:34:18

建议重写

因为一般思路对了都不止 7 分的

by xu_zhihao @ 2024-01-30 18:34:41

@Algorithm_ZRF 也只是建议

by Algorithm_ZRF @ 2024-01-30 18:40:40

@xu_zhihao 这代码能改吗？

by xu_zhihao @ 2024-01-30 18:44:13

@Algorithm_ZRF 问题是 TLE 还是啥

我不敢交，怕被判作弊

by Algorithm_ZRF @ 2024-01-30 18:45:03

@xu_zhihao WA

by xu_zhihao @ 2024-01-30 18:48:06

我吃完饭看看吧

by danlao @ 2024-01-30 19:02:42

@Algorithm_ZRF 你这段代码怎么一样啊？

if(now.t == maxt && farm[now.x][now.y] == 1){
            break;
        }
        if(now.t == maxt && farm[now.x][now.y] == 1){
            return now.t;
        }

by Algorithm_ZRF @ 2024-01-30 19:06:47

@yaodiguoan 谢谢

by Algorithm_ZRF @ 2024-01-30 19:08:09

@yaodiguoan 改了，还是WA

by Algorithm_ZRF @ 2024-01-30 19:14:36

改成了这个样子，#2AC，其余RE


#include <bits/stdc++.h>
using namespace std;
const int maxm = 50005,maxn = 305;
int dx[] = {1,-1,0,0},
    dy[] = {0,0,1,-1};
struct meteor{
    int x,y,t;
}met[maxm];
int farm[maxn][maxn];
struct ss{
    int x,y,t;
};
int m;
inline void Read(){
    cin >> m;
    for(int i = 1;i <= m;++i){
        cin >> met[i].x >> met[i].y >> met[i].t; 
    }
}

inline int bfs(int x,int y,int t){
    queue<ss> q;
    ss s;//初始值
    s.x = x;
    s.y = y;
    s.t = t;
    q.push(s);
    priority_queue<int,vector<int>,less<int>> p;
    for(int i = 1;i <= m;++i){
        p.push(met[i].t);
    }
    int maxt = p.top();
    while(!q.empty()){
        ss now = q.front();
        q.pop();
        for(int i = 1;i <= m;++i){
            if(now.t == met[i].t){
                farm[met[i].x][met[i].y] = 1;
                farm[met[i].x+1][met[i].y] = 1;
                farm[met[i].x-1][met[i].y] = 1;
                farm[met[i].x][met[i].y+1] = 1;
                farm[met[i].x][met[i].y-1] = 1; 
            }
        }
        if(now.t == maxt && farm[now.x][now.y] == 1){
            break;
        }
        if(now.t == maxt && farm[now.x][now.y] == 0){
            return now.t;
        }
        for(int i = 0;i < 4;++i){
            int tx = now.x + dx[i],
                ty = now.y + dy[i],
                tt = now.t + 1;
            if(tx < 0 || ty < 0) continue;//判断越界
            if(farm[tx][ty] == 1)continue;//判断此地是否有陨石砸过
            if(farm[tx][ty] == 2)continue;//判断此地是否已经走过
            farm[tx][ty] = 2; 
            q.push({tx,ty,tt}); 
        }
    } 
    return -1;
}

inline void solve(){
    Read();
    cout << bfs(0,0,0);
}

signed main(){
    solve();
    exit(0);
}
#include <bits/stdc++.h>
using namespace std;
const int maxm = 50005,maxn = 305;
int dx[] = {1,-1,0,0},
    dy[] = {0,0,1,-1};
struct meteor{
    int x,y,t;
}met[maxm];
int farm[maxn][maxn];
struct ss{
    int x,y,t;
};
int m;
inline void Read(){
    cin >> m;
    for(int i = 1;i <= m;++i){
        cin >> met[i].x >> met[i].y >> met[i].t; 
    }
}

inline int bfs(int x,int y,int t){
    queue<ss> q;
    ss s;//初始值
    s.x = x;
    s.y = y;
    s.t = t;
    q.push(s);
    priority_queue<int,vector<int>,less<int>> p;
    for(int i = 1;i <= m;++i){
        p.push(met[i].t);
    }
    int maxt = p.top();
    while(!q.empty()){
        ss now = q.front();
        q.pop();
        for(int i = 1;i <= m;++i){
            if(now.t == met[i].t){
                farm[met[i].x][met[i].y] = 1;
                farm[met[i].x+1][met[i].y] = 1;
                farm[met[i].x-1][met[i].y] = 1;
                farm[met[i].x][met[i].y+1] = 1;
                farm[met[i].x][met[i].y-1] = 1; 
            }
        }
        if(now.t == maxt && farm[now.x][now.y] == 1){
            break;
        }
        if(now.t == maxt && farm[now.x][now.y] == 0){
            return now.t;
        }
        for(int i = 0;i < 4;++i){
            int tx = now.x + dx[i],
                ty = now.y + dy[i],
                tt = now.t + 1;
            if(tx < 0 || ty < 0) continue;//判断越界
            if(farm[tx][ty] == 1)continue;//判断此地是否有陨石砸过
            if(farm[tx][ty] == 2)continue;//判断此地是否已经走过
            farm[tx][ty] = 2; 
            q.push({tx,ty,tt}); 
        }
    } 
    return -1;
}

inline void solve(){
    Read();
    cout << bfs(0,0,0);
}

signed main(){
    solve();
    exit(0);
}```

| 下一页