dfs 71分 5,9,12,14wa求调

P2895 [USACO08FEB] Meteor Shower S

xcwbcgs @ 2024-03-04 18:29:00

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int t[350][350];
int ind[350][350];
int f[350][350];
int minn=23333;
int min(int a,int b){
    if(a<b)return a;
    else return b;
}
void search(int a,int b,int x){
    if(x>=minn)return;
    if(a<0||b<0)return;
    if(x>=t[a][b]||ind[a][b]!=0||x>=f[a][b])return;
    if(t[a][b]==23333){
        minn=min(x,minn);
        return;
    }
    f[a][b]=x;
    ind[a][b]=1;
    search(a+1, b, x+1);
    search(a-1, b, x+1);
    search(a, b+1, x+1);
    search(a, b-1, x+1);
    ind[a][b]=0;
}
int main(){
    int m;
    scanf("%d",&m);
    int i,j;
    for(i=0;i<350;i++){
        for(j=0;j<350;j++){
            t[i][j]=23333;
            f[i][j]=23333;
        }
    }
    for(i=0;i<m;i++){
        int x,y,time;
        scanf("%d %d %d",&x,&y,&time);
        t[x][y]=time;
        if((x-1)<0){
            if((y-1)<0){
                t[x+1][y]=min(time,t[x+1][y]);
                t[x][y+1]=min(time,t[x][y+1]);
            }
            else{
                t[x+1][y]=min(time,t[x+1][y]);
                t[x][y+1]=min(time,t[x][y+1]);
                t[x][y-1]=min(time,t[x][y-1]);
            }
        }
        else{
            if((y-1)<0){
                t[x+1][y]=min(time,t[x+1][y]);
                t[x-1][y]=min(time,t[x-1][y]);
                t[x][y+1]=min(time,t[x][y+1]);
            }
            else{
                t[x+1][y]=min(time,t[x+1][y]);
                t[x-1][y]=min(time,t[x-1][y]);
                t[x][y+1]=min(time,t[x][y+1]);
                t[x][y-1]=min(time,t[x][y-1]);
            }
        }
    }
    search(0, 0, 0);
    if(minn==23333)printf("-1");
    else printf("%d",minn);
    return 0;
}

by wobuhuiqiming @ 2024-04-04 19:35:49

t[x][y]=time; 接收数据这里也要用t[x][y]=min(t[x][y],time)


|