本地过了但几个点REQwQ

lucy2012 @ 2024-04-17 21:06:11

#include<bits/stdc++.h>
using namespace std;
struct where{
    int x,y;
};
queue<where> q;
int sum[310][310],when[310][310];
int d[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
void minn(int a,int b,int c){
    if(a>=0&&b>=0)
        when[a][b]=min(when[a][b],c);
}
int main(){
    int m,ans=100000;
    memset(sum,-1,sizeof(sum));
    memset(when,0x7f,sizeof(when));
    cin>>m;
    for(int i=1;i<=m;i++){
        int x,y,t;
        cin>>x>>y>>t;
        minn(x,y,t);
        for(int k=0;k<4;k++)
            minn(x+d[k][0],y+d[k][1],t);
    }
    q.push((where){0,0});
    sum[0][0]=0;
    while(!q.empty()){
        where u=q.front();
        int ux=u.x,uy=u.y;
        q.pop();
        for(int k=0;k<4;k++){
            int x1=ux+d[k][0],y1=uy+d[k][1];
            if(x1<0||y1<0||sum[x1][y1]!=-1||sum[ux][uy]+1>=when[x1][y1])
                continue;
            sum[x1][y1]=sum[ux][uy]+1;
            where wh={x1,y1};
            q.push(wh);
        }
    }
    for(int i=0;i<=305;i++){
        for(int j=0;j<=305;j++){
            if(when[i][j]>1000&&sum[i][j]!=-1)
                ans=min(ans,sum[i][j]);
        }
    }
    if(ans==100000)
        cout<<-1;
    else
        cout<<ans;
    return 0;
}

by lucy2012 @ 2024-04-17 21:29:39

改这样就ac了诶，为什么？

#include<bits/stdc++.h>
using namespace std;
struct where{
    int x,y;
};
queue<where> q;
int sum[400][400],when[400][400];
int d[4][2]={{0,1},{1,0},{-1,0},{0,-1}};
void minn(int a,int b,int c){
    if(a>=0&&b>=0)
        when[a][b]=min(when[a][b],c);
}
int main(){
    int m,ans=100000;
    memset(sum,-1,sizeof(sum));
    memset(when,0x7f,sizeof(when));
    cin>>m;
    for(int i=1;i<=m;i++){
        int x,y,t;
        cin>>x>>y>>t;
        minn(x,y,t);
        for(int k=0;k<4;k++)
            minn(x+d[k][0],y+d[k][1],t);
    }
    q.push((where){0,0});
    sum[0][0]=0;
    while(!q.empty()){
        where u=q.front();
        int ux=u.x,uy=u.y;
        q.pop();
        for(int k=0;k<4;k++){
            int x1=ux+d[k][0],y1=uy+d[k][1];
            if(x1<0||y1<0||sum[x1][y1]!=-1||sum[ux][uy]+1>=when[x1][y1])
                continue;
            sum[x1][y1]=sum[ux][uy]+1;
            where wh={x1,y1};
            q.push(wh);
        }
    }
    for(int i=0;i<=305;i++){
        for(int j=0;j<=305;j++){
            if(when[i][j]>1000&&sum[i][j]!=-1)
                ans=min(ans,sum[i][j]);
        }
    }
    if(ans==100000)
        cout<<-1;
    else
        cout<<ans;
    return 0;
}

by lhj18313744014 @ 2024-04-23 19:23:23

#include<bits/stdc++.h>//HGFNHGFNHJNHGFNHGNHGNHGF 
using namespace std;//HGCNHGNMHKUINUYMGFJHG FGHY
int n,ma[305][305],v[305][305],sx,sy,st,ans[305][305];//BNF JHMKJ,KHMJMJHKMJHJMJGHMMJHG
int dx[5]={0,0,0,1,-1};//MNG HJMMJJUYTYUJMFYUMKJUYTKKUYTI
int dy[5]={0,1,-1,0,0};//,JKHKJ,IKYUKYTUKYKUYTUKYUKY
int ch(int a){//YJMTKTIYTUKKTUTUKJTKKUYIT
    if (a==-1) return 99999;//NJMHGHJMJHMJHMJHMJHGMJHGMK,YUJGK
    else return a;//GBFGBFGBFDFGHNNHGNGT
}//FDGHGFNDTRHHTRHTYR
int main(){//HGYRYUTRUYRYURUYRUY
    scanf("%d",&n);//GHFHJGFHJFJHFJYFJ
    for (int i=0;i<305;i++){//HFHJFGHFHGFGDFGDFGDTHDFGDRTRTER
        for (int j=0;j<305;j++){//GFYHFYHFHHGGCFGNFGHFDJFHJHJTUGJKGHJG
            ma[i][j]=-1;//GHJFHFGFDRTDRTERFGSERTTTTTTTTTTTTTTTTTTTTTTTTTTTTTT
            //GGHJGFFGHDDFHJFJHHJHGHGHJHFGHF
        }//AFGHWQ2DFGHEWFCFREJGF
    }//ASBFDJKEGJHFGSAHJFYUERHYFREYTYESGFJ
    for (int i=1;i<=n;i++){//GERHJFHRHGFYERFYUFGERUSYTFUYERWTDYUEWFRYUWT
        scanf("%d%d%d",&sx,&sy,&st);//NDEGHJKTRHGFUREGUFREGHREHGHTRUHUGUREHFUHU
        for (int j=0;j<5;j++){//HDGHSJVGFGDCGFDVGGDHSBCHJDGFSHJ
            if (sx+dx[j]>=0&&sy+dy[j]>=0&&(ma[sx+dx[j]][sy+dy[j]]==-1||ma[sx+dx[j]][sy+dy[j]]>st))
                ma[sx+dx[j]][sy+dy[j]]=st;
        } 
    }
    queue<int> q[2];
    v[0][0]=1;
    q[0].push(0);q[1].push(0);
    while (!q[0].empty()){
        int x=q[0].front(),y=q[1].front();
        q[0].pop();q[1].pop();
        int s=ans[x][y]+1;
        if (ma[x][y]==-1){ 
            printf("%d\n",s-1);
            return 0;
        }
        for (int i=1;i<=4;i++){
            int xx=x+dx[i],yy=y+dy[i];
            if (xx>=0&&yy>=0&&s<ch(ma[xx][yy])&&v[xx][yy]==0){
                q[0].push(xx);q[1].push(yy);
                v[xx][yy]=1;
                ans[xx][yy]=s;
            }
        }
    }
    printf("-1\n");
    return 0;
}