题解 P2802 【回家(quan shui)】

· · 题解

深搜大法好！！！

看了看前辈和dalao的题解，总感觉判断条件上有点小繁琐。再加上坐旁边的大(di)神(di)都已经写了他们的第一篇题解，作为蒟蒻的我看了很羡(ji)慕(du)，所以我也写(shui)一篇(bo)。

题目的大致意思就是一个被追着跑的亚索需要跑回泉水。

0=地形，1=路，2=开始的位置，3=泉水，4=小兵。

条件给的范围是[0,15],所以放心大胆的用(xiong)搜(qian)索(E)。

存储方式：map[N][N]存图,book[N][N]用来判断。

下面直接上代码。

#include<cstdio>
#define N 11
int stx,sty,enx,eny,map[N][N],book[N][N],n,m,min=9999999;
const int next[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
//分别向右、向下、向左、向上走
bool can；
//是否能到达

void dfs(int step,int x,int y,int remain)
{
   int i,tx,ty;
   if(remain==0)return;//血流完了
   if(step>=min)return;//剪枝
   if(x==enx&&y==eny){//到达目的地
      if(min>step)min=step;//更新最小值
      if(can==0)can=1;
      return;
   }
   for(i=0;i<=3;i++){
   //枚举各个方向
      tx=x+next[i][0],ty=y+next[i][1];
      if(tx<1||tx>n||ty<1||ty>m||map[tx][ty]==0)continue;
      //不能走出地图也不能买挂变凯隐
      if(book[tx][ty]==0){
         book[tx][ty]=1;
         if(map[tx][ty]==4&&remain>1)dfs(step+1,tx,ty,6);
         //有小兵,往前E刷盾(注意remain>1，没死才能E！)
         else dfs(step+1,tx,ty,remain-1);
         //没小兵，继续用脚赶路
         book[tx][ty]=0;
      }
   }
   return;
}

int main()
{
   int i,j;
   scanf("%d%d",&n,&m);
   for(i=1;i<=n;i++)
      for(j=1;j<=m;j++){
         scanf("%1d",&map[i][j]);
         if(map[i][j]==2)stx=i,sty=j;
         else if(map[i][j]==3)enx=i,eny=j;
      }
   book[stx][sty]=1;
   dfs(0,stx,sty,6);
   if(can)
      printf("%d",min);
   else
      printf("-1");
   return 0;
}