求助 #10 之后MLE了

QingQiu1 @ 2023-12-08 17:02:21

#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
const int N = 310;
typedef pair<int,int> pii;
int g[N][N]/*记录最早掉落流星的时间,*/;
bool vis[N][N];//最早到这个点的时间
int dx[5] = {0,0,-1,0,1};
int dy[5] = {0,1,0,-1,0};
int ma = 0;
void init(int t ,int x ,int y) {
    for (int i = 0 ; i < 5 ; i ++) {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 0 || ny < 0) continue;
        g[nx][ny]  =  min(g[nx][ny],t);
    }
}
int bfs() {
    if(g[0][0] == 0) return -1;
    vis[0][0] = true;
    queue<pii> q;
    q.push({0,0});
    int t = 1;
    while(!q.empty()) {
        int len = q.size();
        while(len --) {
            pii temp = q.front();
            q.pop();
            int x = temp.first , y = temp.second;
            for (int i = 1 ; i < 5 ; i ++) {
                int nx = x + dx[i], ny = y + dy[i];
                if(nx < 0 || ny < 0 || vis[nx][ny] || t >= g[nx][ny]) continue;
                q.push({nx,ny});
                if(g[nx][ny] == 0x3f3f3f3f) return t;
            }
        }   
        t ++;
    }
    return - 1;
}
int main() {
    int m;
    cin >> m;
    memset(g,0x3f,sizeof g);
    for (int i = 0 ; i < m ; i ++) {
        if(g[0][0] == 0) {
            cout << "-1" <<endl;
            return 0;
        }
        int t , x , y;
        scanf("%d%d%d",&x,&y,&t);
        init(t,x,y);
    }
    cout << bfs();
    return 0;
}

by QingQiu1 @ 2023-12-08 17:30:30

@htlove 解决了，忘记给vis等于 true了 AC代码:

#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
const int N = 400;
typedef pair<int,int> pii;
int g[N][N]/*记录最早掉落流星的时间,*/;
bool vis[N][N];//最早到这个点的时间
int v[N][N];
int dx[5] = {0,0,-1,0,1};
int dy[5] = {0,1,0,-1,0};
void init(int t ,int x ,int y) {
    for (int i = 0 ; i < 5 ; i ++) {
        int nx = x + dx[i], ny = y + dy[i];
        if(nx < 0 || ny < 0) continue;
        g[nx][ny]  =  min(g[nx][ny],t);
    }
}
int bfs() {
    vis[0][0] = true;
    queue<pii> q;
    q.push({0,0});
    v[0][0] = 0;
    while(!q.empty()) {
        pii temp = q.front();
        q.pop();
        int x = temp.first , y = temp.second;
        for (int i = 1 ; i < 5 ; i ++) {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < 0 || ny < 0 || vis[nx][ny] || v[x][y] + 1 >= g[nx][ny]) continue;
            v[nx][ny] = v[x][y] + 1;
            q.push({nx,ny});
            vis[nx][ny] = true;
            if(g[nx][ny] == 0x3f3f3f3f) return v[nx][ny];
        }
    }
    return - 1;
}
int main() {
    int m;
    cin >> m;
    memset(g,0x3f,sizeof g);
    for (int i = 0 ; i < m ; i ++) {
        if(g[0][0] == 0) {
            cout << "-1" <<endl;
            return 0;
        }
        int t , x , y;
        scanf("%d%d%d",&x,&y,&t);
        init(t,x,y);
    }
    cout << bfs();
    return 0;
}