为什么我是TLE?!

P2895 [USACO08FEB] Meteor Shower S

lg128 @ 2024-08-21 15:10:58

为什么是TLE啊。。。

样例1-9AC

样例10--14全部tle

代码如下:

#include <iostream>
#include <cstring>
using namespace std;
bool vis[310][310];
int map[310][310];
int m,x,y,t;
int r[4]={-1,0,1,0},c[4]={0,1,0,-1};
int minn=1020;
void dfs(int i,int j,int time){
    if(map[i][j]==-1){
        minn=min(minn,time);
        return ;
    }
    if(time>=map[i][j]) return ;
    int ni,nj;
    for(int k=0;k<4;k++){
        ni=i+r[k],nj=j+c[k];
        if(ni>=0&&nj>=0&&!vis[ni][nj]){
            vis[ni][nj]=1;
            dfs(ni,nj,time+1);
            vis[ni][nj]=0;
        }
    }
}
int main(){
    cin>>m;
    memset(map,-1,sizeof map);
    while(m--){
        cin>>x>>y>>t;
        if(map[x][y]==-1) map[x][y]=t;
        else map[x][y]=min(map[x][y],t);
        int nx,ny;
        for(int i=0;i<4;i++){
            nx=x+r[i],ny=y+c[i];
            if(nx>=0&&nx<=300&&ny>=0&&ny<=300){
                if(map[nx][ny]==-1) map[nx][ny]=t;
                else map[nx][ny]=min(map[nx][ny],t);
            }
        }
    }
    vis[0][0]=1;
    dfs(0,0,0);
    if(minn>=1000) cout<<-1<<endl;
    else cout<<minn;
    return 0;
}

by ACehomoxue @ 2024-08-21 15:17:32

改用scanf和bfs应该就能过了


by lg128 @ 2024-08-23 07:10:52

@ACehomoxue 您好!为什么dfs不行啊,已关注


by Lester_y1 @ 2024-08-23 22:41:31

dfs搜完所有情况才会结束,bfs搜到的第一个情况一定是最优解,就可以返回了


|