lg128 @ 2024-08-21 15:10:58
样例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搜到的第一个情况一定是最优解,就可以返回了