回家

玉竹君 · 2019-01-02 17:52:55 · 题解

这道题其实就是分析几种出不去的情况，然后就是要排除（回溯到上一步）。首先，第一种情况就是可以走的地方是个障碍（0）；第二种是血量没了；第三种是走出了边界 所以这样：

if(M[x][y]==0 || !now || !vis[x][y])
    {
        return ;    
    }
    if(x<1 || x>n || y<1 || y>m)
    return ;

这样就解决了所有不成立的情况，然后我们接下来就要选取最优情况的答案； 方法就是取小，我们把每次的答案都取小保存，然后在返回去找还有没有更简单的答案：

if(M[x][y]==3)
    {
        Min=min(tot , Min);
        return ;
    }

接下来就是要看回血的情况了 代码很简单，就是把血补满就好了； 然后就要走下一步的部分，四个方向，每次都要扣血，并且要记步，标记是否走过，我们要把走过的路都排除，因为肯定不会是最简。 这部分代码如下：

int now1=now-1;
    if(M[x][y]==4)
    {
        now1=5;
    }
    vis[x][y]=0;
    dfs(x+1,y,tot+1,now1);
    dfs(x-1,y,tot+1,now1);
    dfs(x,y+1,tot+1,now1);
    dfs(x,y-1,tot+1,now1);
    vis[x][y]=1;

下面就是总的代码啦！

#include<bits/stdc++.h>
using namespace std;
int M[10][10],n,m,Min = 9999999;
bool vis[10][10];
void dfs(int x,int y,int tot,int now)
{
    if(M[x][y]==0 || !now || !vis[x][y])
    {
        return ;    
    }
    if(x<1 || x>n || y<1 || y>m)
    return ;
    if(tot > Min) //前面忘记说了，因为可能会走到一个很绕的路，所以“剪枝”，把已经超过当前值的排除。
    return ;
    if(M[x][y]==3)
    {
        Min=min(tot , Min);
        return ;
    }

    int now1=now-1;
    if(M[x][y]==4)
    {
        now1=5;
    }
    vis[x][y]=0;
    dfs(x+1,y,tot+1,now1);
    dfs(x-1,y,tot+1,now1);
    dfs(x,y+1,tot+1,now1);
    dfs(x,y-1,tot+1,now1);
    vis[x][y]=1;
}
int main(){
    int a,b;
    scanf("%d%d",&n,&m);
    memset(vis,true,sizeof(vis));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&M[i][j]);
            if(M[i][j]==2)//记录下起点
            {
                a=i;
                b=j;
            }

        }
    dfs(a,b,0,6);   
    if(Min==9999999)
    printf("%d",-1);//这种是完全走不出去的
    else
    printf("%d",Min);   
    return 0;
}