xibaohe @ 2022-07-26 22:43:34
#include<bits/stdc++.h>//万能头文件
using namespace std;
int m,mp[505][505],ans;
//m如题意表示,mp数组表示该位置是否会有流星降落及降落时间,ans表示最少移动时间
bool flag=false,vis[505][505];
//flag表示若搜到答案就不再搜索,vis数组表示该位置是否已被访问
void search(int x,int y,int step)//x、y表示坐标,step表示所用时间
{
if(x<1||y<1||x>505||y>505)
return;//若超出范围,结束搜索
if(flag==true)
return;//若已有答案,结束搜索
if(vis[x][y]==true)
return;//若已被访问,结束搜索
if(mp[x][y]!=-1&&mp[x][y]<=step)
return;//若已被袭击,结束搜索
if(mp[x][y]==-1)//递推边界
{
ans=step;//记录最小值
flag=true;//标记为已有答案
return;//结束搜索
}
vis[x][y]=true;//标记已访问
search(x+1,y,step+1);//搜索右边的点
search(x,y+1,step+1);//搜索下边的点
search(x-1,y,step+1);//搜索左边的点
search(x,y-1,step+1);//搜索上边的点
vis[x][y]=false;//回溯
}
int main(){
cin>>m;//输入
memset(mp,-1,sizeof(mp));//把mp数组赋初值为-1
for(int i=1;i<=m;i++)
{
int x,y,t;//x、y表示坐标,t表示到达时间
cin>>x>>y>>t;//输入
mp[x][y]=t;//当前的点t时被毁灭
mp[x+1][y]=t;//右边的点t时被毁灭
mp[x-1][y]=t;//左边的点t时被毁灭
mp[x][y+1]=t;//下边的点t时被毁灭
mp[x][y-1]=t;//上边的点t时被毁灭
}
search(0,0,0);//从原点出发,时间为0,开始搜索
if(flag==false)//如果没搜到答案,输出-1
{
cout<<-1<<endl;
}
else//如果搜到答案,输出ans
{
cout<<ans<<endl;
}
return 0;
}
by Eydte @ 2022-07-26 23:05:35
你不能一搜到就停止啊,不一定是最小啊
by Eydte @ 2022-07-26 23:06:29
而且最好再进一步搜索前就判断是否合法,而不是递归了再返回
by xibaohe @ 2022-07-27 09:15:31
@_EDC 谢谢!我改正一下!