题解 P2802 【回家】

Teacher_Xiao · 2019-07-27 11:32:46 · 题解

一. 这个题目其实就是简单的DFS运用遍历所有条件即可但是有几点需要注意的地方

1.退出条件需要注意，一开始我设置了一个极大数来退出，后面发现完全没有必要，只需要设置大于N*M，F==0和sum》sums及可。

2. 要先判断血量在来判断目标位置上有什么东西。 只要注意一下，然后直接暴搜就好 以下为源代码

   
   #include <iostream>
   #include <string.h>
   #include <algorithm>
   #include <stdio.h>
   #include <queue>
   #include<math.h>
   using namespace std;
   int a[20][20];//存储地图
   int dx[4]={1,-1,0,0};
   int dy[4]={0,0,1,-1};//移动方向
   int sum=0,sums=555555;
   int s=1;
   int x,y;//存储初始位置
   int ex,ey;//存储终点位置
   int n,m;
   void DFS(int x,int y,int f)
   {
   if(f==0||sum>n*m||sum>sums)
   {
       return ;
   }
   if(a[x][y]==4)
   {
       f=6;
   }
   if(x==ex&&y==ey)
   {
       s=0;
       sums=min(sum,sums);
       return ;
   }
   for(int k=0;k<4;k++)
   {
       int i,j;
       i=x+dx[k];
       j=y+dy[k];
       if(a[i][j]!=0&&i>=0&&j>=0&&i<n&&j<m)
       {
           sum++;
           DFS(i,j,f-1);
           sum--;
       }
   }
   }
   int main()
   {
   
   cin>>n>>m;
   int f=6;
   memset(b,0,sizeof(b));
   for(int i=0;i<n;i++)
   {
       for(int j=0;j<m;j++)
       {
           cin>>a[i][j];
           if(a[i][j]==2)
           {
               x=i;
               y=j;
           }
           if(a[i][j]==3)
           {
               ex=i;
               ey=j;
           }
       }
   }
   DFS(x,y,f);
   if(s==0)
   {
       cout<<sums<<endl;
   }
   else
   {
       cout<<"-1"<<endl;
   }
   return 0;
   }