我的样例输出为什么是3,求大佬指正

P2895 [USACO08FEB] Meteor Shower S

renhongtu @ 2023-12-06 19:53:22

#include<bits/stdc++.h>
using namespace std;

bool vis[305][305]; 

int m;
int fuzhu[305][305]={0};
typedef struct sss{
    int x,y,t;
}sss;
int d[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
sss star[50005];
typedef struct ren{
    int rx,ry;
}ren;//贝茜 
ren b;
bool compare(sss s1,sss s2){
    return s1.t<s2.t;
}
void bfs(int sx, int sy, int tt) {
    queue<ren> q;

    q.push({sx, sy});
    vis[sx][sy] = true; // 初始位置已访问
    int step = 1;

    while (!q.empty()) {
        int size = q.size(); // 当前层的节点数量

        // 更新星星爆炸影响的区域
        while (step <= m && star[step].t == tt) {

            for (int k = 0; k < 4; ++k) {
                int nx = star[step].x + d[k][0];
                int ny = star[step].y + d[k][1];
                if (nx >= 0 && nx <= 300 && ny >= 0 && ny <= 300) {
                    vis[nx][ny]=true;
                }
            }
             vis[star[step].x][star[step].y]=true;
            // 爆炸点本身也是危险的

            step++;
        }
        for (int i = 0; i < size; ++i) { // 遍历当前层的所有节点
            ren c = q.front(); q.pop();

            // 如果当前位置是安全的,输出答案并返回
            if (fuzhu[c.rx][c.ry] == 0) {
                cout << tt << endl;
                return;
            }

            // 尝试四个方向移动
            for (int j = 0; j < 4; ++j) {
                int dx = c.rx + d[j][0];
                int dy = c.ry + d[j][1];
                if (dx >= 0 && dx <= 300 && dy >= 0 && dy <= 300 && !vis[dx][dy]) {
                    q.push({dx, dy});
                    vis[dx][dy] = true; // 标记为已访问
                }
            }
        }

        tt++; // 时间增加

    }

    // 如果队列为空,说明没有找到安全路径
    cout << "-1" << endl;
}

int main(){
    cin>>m;
    for(int i=1;i<=m;++i){
        cin>>star[i].x>>star[i].y>>star[i].t;
        fuzhu[star[i].x][star[i].y]=1;
        fuzhu[star[i].x-1][star[i].y]=1;//辅助数组为0的地方是永远安全的 
        fuzhu[star[i].x+1][star[i].y]=1;
        fuzhu[star[i].x][star[i].y-1]=1;
        fuzhu[star[i].x][star[i].y+1]=1;
    }
    sort(star+1,star+1+m,compare);
    bfs(0,0,0);
    return 0;
}

by renhongtu @ 2023-12-06 19:53:52

求指正


by 13288917088c @ 2023-12-25 13:11:02

1, 建议建一个int数组,存储该点被砸中的最短时间,因为流星是在逃离过程中砸下来的,如果在走到该点时(或之前),该点已经烧焦了,则直接continue。

2, 在到达其他点时提前判断是否永远安全,或者已经毁灭,优化内存(我就因为这点MLE了)

自己改代码,我的就不打出来了。


by 13288917088c @ 2023-12-25 13:11:36

@renhongtu


by 13288917088c @ 2023-12-25 13:13:34

虽然我很弱,但可以看一下


by 13288917088c @ 2023-12-25 13:14:21

给个关注QWQ


by 13288917088c @ 2023-12-25 13:16:15

好吧,我俩好像差不多(刚刚看了你的数据)


by 13288917088c @ 2023-12-25 13:22:31

我是学生党,可能不能及时回复


|