MLE+WA求调

jinminghao @ 2024-09-26 20:29:47

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=310;
struct Node{
    int x,y,sum;
};
int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int a[N][N];
queue<Node> q;
int bfs(){
    Node v;
    v.x=0; v.y=0; v.sum=0;
    q.push(v);
    while(!q.empty()){
        Node t=q.front();
        q.pop();
        int tx=t.x,ty=t.y,res=t.sum;
        if(a[tx][ty]==-1) return res;
        for(int i=0;i<4;i++){
            int nx=tx+dx[i],ny=ty+dy[i];
            if(nx>=0&&ny>=0&&(a[nx][ny]==-1||a[nx][ny]>res+1)){
                Node k;
                k.x=nx; k.y=ny; k.sum=res+1;
                q.push(k);
            }
        }
    }
    return -1;
}
int main(){
    memset(a,-1,sizeof a);
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int x,y,t;
        scanf("%d%d%d",&x,&y,&t);
        a[x][y]=t;
        for(int j=0;j<4;j++){
            int tx=x+dx[j],ty=y+dy[j];
            if(tx>=0&&ty>=0){
                if(a[tx][ty]==-1) a[tx][ty]=t;
                else a[tx][ty]=min(a[tx][ty],t);
            }
        }
    }
    int ans=bfs();
    printf("%d",ans);
    return 0;
}

by lingquan @ 2024-09-30 15:58:19

WA的点是因为第41行初始化a数组被砸的点时a[x][y]没有判断最小的被砸时间

by lingquan @ 2024-09-30 16:27:08

MLE是因为重复搜点，有两种解决办法：\ 1、定义flag数组判断是否重复搜点；\ 2、a[x][y]=res+1；

by lingquan @ 2024-09-30 16:30:50

AC代码如下： \ \ \ \ flag数组写法：

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=310;

struct Node{
    int x,y,sum;
};

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int a[N][N];
bool flag[N][N];
queue<Node> q;

int bfs(){
    q.push({0,0,0});
    flag[0][0]=1;
    while(!q.empty()){
        Node t=q.front();
        q.pop();
        int res=t.sum;
        for(int i=0;i<4;i++){
            int nx=t.x+dx[i],ny=t.y+dy[i];
            if(nx>=0 && nx<=310 && ny>=0 && ny<=310 && flag[nx][ny]==0){
                if(a[nx][ny]==-1){
                    return res+1;
                }else{
                    if(a[nx][ny]>res+1){
                        flag[nx][ny]=1;
                        q.push({nx,ny,res+1});
                    }
                }
            }
        }
    }
    return -1;
}

int main(){
    memset(a,-1,sizeof a);
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int x,y,t;
        scanf("%d%d%d",&x,&y,&t);
        a[x][y]==-1?a[x][y]=t:a[x][y]=min(a[x][y],t);
        for(int j=0;j<4;j++){
            int tx=x+dx[j],ty=y+dy[j];
            if(tx>=0 && ty>=0){
                if(a[tx][ty]==-1) a[tx][ty]=t;
                else a[tx][ty]=min(a[tx][ty],t);
            }
        }
    }
    int ans=bfs();
    printf("%d",ans);
    return 0;
}

\ \ a[x][y]=res+1写法：

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
const int N=310;

struct Node{
    int x,y,sum;
};

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};
int a[N][N];
queue<Node> q;

int bfs(){
    q.push({0,0,0});
    while(!q.empty()){
        Node t=q.front();
        q.pop();
        int res=t.sum;
        for(int i=0;i<4;i++){
            int nx=t.x+dx[i],ny=t.y+dy[i];
            if(nx>=0 && nx<=310 && ny>=0 && ny<=310){
                if(a[nx][ny]==-1){
                    return res+1;
                }else{
                    if(a[nx][ny]>res+1){
                        a[nx][ny]=res+1;
                        q.push({nx,ny,res+1});
                    }
                }
            }
        }
    }
    return -1;
}

int main(){
    memset(a,-1,sizeof a);
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int x,y,t;
        scanf("%d%d%d",&x,&y,&t);
        a[x][y]==-1?a[x][y]=t:a[x][y]=min(a[x][y],t);
        for(int j=0;j<4;j++){
            int tx=x+dx[j],ty=y+dy[j];
            if(tx>=0 && ty>=0){
                if(a[tx][ty]==-1) a[tx][ty]=t;
                else a[tx][ty]=min(a[tx][ty],t);
            }
        }
    }
    int ans=bfs();
    printf("%d",ans);
    return 0;
}

by jinminghao @ 2024-09-30 19:45:44

@lingquan 谢谢