题解 P2802 【回家】

PTC06 · 2017-01-04 20:23:59 · 题解

数据很水...我一开始提交时每遇到一个4就将血量增加一而不是不满也能有90分..

咳咳，言归正传。

思路：

读入n，m

输入整个地图，用ma这个数组存起来，如果输入的数是2或3就表示是起点/重点，就标记起来。

深搜。其实不会深搜的最好去做P1605 迷宫，是一道很好的题。

void dfs(int x,int y,int health,int tme)        
{
    if (x>n || y>m || x<0 || y<0 || health==0 || book[x][y]==1 || tme>ans || ma[x][y]==0) return;    //判断各种需要return的情况，如越界和已经来过这个格等
    if (x==finx && y==finy)           //到达目的地，判断最小值，存入ans
    {
        if (tme<ans) ans=tme;
    }
    if (ma[x][y]==4) health=6;             //如果是4就捡个鼠标
    book[x][y]=1;                 //标记，当作走过了
    dfs(x-1,y,health-1,tme+1);         //往四个方向走
    dfs(x+1,y,health-1,tme+1);
    dfs(x,y-1,health-1,tme+1);
    dfs(x,y+1,health-1,tme+1);
    book[x][y]=0;             //尝试收回。
}

最后如果ans不是2333就输出ans，否则输出-1（这里我将ans初始值定为2333） 代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,ans,i,j,ma[10][10],finx,finy,startx,starty,book[10][10],tme,health=6;   
void dfs(int x,int y,int health,int tme)
{
    if (x>n || y>m || x<0 || y<0 || health==0 || book[x][y]==1 || tme>ans || ma[x][y]==0) return;
    if (x==finx && y==finy)
    {
        if (tme<ans) ans=tme;
    }
    if (ma[x][y]==4) health=6;
    book[x][y]=1; 
    dfs(x-1,y,health-1,tme+1);
    dfs(x+1,y,health-1,tme+1);
    dfs(x,y-1,health-1,tme+1);
    dfs(x,y+1,health-1,tme+1);
    book[x][y]=0;
}
int main()
{
    cin>>n>>m;
    ans=2333;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=m;j++)
        {
            cin>>ma[i][j];
            if (ma[i][j]==2)
            {
                startx=i;
                starty=j;
            }
            if (ma[i][j]==3)
            {
                finx=i;
                finy=j;
            }
        }
    }
    dfs(startx,starty,6,0);
    if(ans==2333) cout<<-1; else cout<<ans;
}