题解 P2802 【回家】

· · 题解

看了一下楼下各位大神的题解，发现确实有很多人都是在n和m上分不清。。

好吧，我也没分清。。

然后就一直不停错，还找不出来原因。。

最后狠心把所有判断dfs停止的条件单独列出来，终于找到了问题。。。

具体解释看代码：：：

#include<iostream>
using namespace std;
int n,m,ans=10000;//ans的值要赋大一点
int a[15][15],b[15][15];//第一个读入，第二个判断有没有走过
void dfs(int x,int y,int an,int hp){
    if(hp==0||y>m||x>n||x<=0||y<=0||a[x][y]==0||b[x][y]==1||an>ans)return;//判停条件，越界，不是最优解，没有生命值了，有障碍之类的，一定要注意区分n和m，我之前就一直写的是y>n，然后不停70分。
    if(a[x][y]==3){//如果到终点的情况
        ans=min(ans,an);//其实有上面的判断，也可以直接写ans=an，也不会有错
        return;//返回
    }
    if(a[x][y]==4)hp=6;//泉水。。
    b[x][y]=1;//标记走过了
    dfs(x+1,y,an+1,hp-1);//往上走
    dfs(x,y+1,an+1,hp-1);//往右走
    dfs(x-1,y,an+1,hp-1);//往下走
    dfs(x,y-1,an+1,hp-1);//往左走
    b[x][y]=0;//之前标记的，现在去掉
}
int main(){
    int p,q;
    cin>>n>>m;//读入
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];//读入，考场上建议用scanf，比较快
            if(a[i][j]==2)p=i,q=j;//一定要标记起点，不然会错，具体几个点不是很清楚。。。
        }
}
    dfs(p,q,0,6);//调用函数
    if(ans==10000)cout<<-1<<endl;//如果ans值没变，就说明不能到终点，输出-1
    else cout<<ans<<endl;//否则输出步数
    return 0;

}//完美结束 //最后，祝大家编程顺利