求救啊朋友们7分(为了方便大家看我加上了墨迹注释)

P2895 [USACO08FEB] Meteor Shower S

xibaohe @ 2022-07-26 22:43:34

求助啊各位

7分 剩下点全WA

为了方便大家看我加上了墨迹注释

#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 谢谢!我改正一下!


|