首页 > 代码库 > 走迷宫(三):在XX限制条件下,是否走得出。

走迷宫(三):在XX限制条件下,是否走得出。

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1010

题目前提条件:让你输入一个数组,包含一个起点S,一个终点D,一个时间T。(其中X代表墙,.代表此地可行。)

题目要求:在规定的第T秒,问你是否能够走出迷宫。(每走一步耗时1s)。

解题方法:DFS+vis[][]+flag+(新技巧)奇偶剪枝。

 

#include<iostream>
#include<string.h>
#include<cmath>;
using namespace std;

char map[8][8];
int vis[8][8];  //(新增)访问标记的数组
int N,M,T;           
int sx,dx,sy,dy;
int flag;      //(新增)判断状态
int k;         //(新增)记录障碍物的个数

int abs(int a,int b)
{
    if(a<b)
    {
        return b-a;
    }
    else
    {
        return a-b;
    }
}

void dfs(int x,int y,int dep)   //void()函数内使用“return;”表示跳出此函数。
{
    if(dep>T)                       
    {
        return ;            
    }
    if(x<0||x>=N||y<0||y>=M)     
    {
        return ;
    }


    if(flag)                       
    {
        return;
    }
    if(map[x][y]==D&&dep==T)    
    {
        flag=1;
        return ;
    }


    int temp=abs(x-dx)+abs(y-dy); //(新增)奇偶剪枝
    temp=T-temp-dep;
    if(temp&1)                    //if(走不下去了)
    {
        return;
    }


    //枚举下一种情况,DFS(...,dep+1);
   if(!vis[x-1][y]&&map[x-1][y]!=X)    //(新增)if(下一个点满足的情况)
   {
       vis[x-1][y]=1;    
       dfs(x-1,y,dep+1);
       vis[x-1][y]=0;     
   }
   if(!vis[x+1][y]&&map[x+1][y]!=X)   //(新增)if(下一个点满足的情况)
   {
       vis[x+1][y]=1;   
       dfs(x+1,y,dep+1);
       vis[x+1][y]=0;   
   }
   if(!vis[x][y-1]&&map[x][y-1]!=X)   //(新增)if(下一个点满足的情况)
   {
       vis[x][y-1]=1; 
       dfs(x,y-1,dep+1);
       vis[x][y-1]=0;   
   }
   if(!vis[x][y+1]&&map[x][y+1]!=X)   //(新增)if(下一个点满足的情况)
   {
       vis[x][y+1]=1;   
       dfs(x,y+1,dep+1);
       vis[x][y+1]=0;   
   }

}

int main()
{
    while(cin>>N>>M>>T)
    {
        if(N==0&&M==0&&T==0)
        {
            break;
        }

        k=0;         
        memset(vis,0,sizeof(vis));   //(新增)访问标记数组的初始化。

        for(int i=0;i<N;i++)
        {
            for(int j=0;j<M;j++)
            {
                cin>>map[i][j];
                if(map[i][j]==S)
                {
                    sx=i;
                    sy=j;
                    vis[i][j]=1;  //(新增)给起点作“已访”标记
                }
                if(map[i][j]==D)
                {
                    dx=i;
                    dy=j;
                }

                if(map[i][j]==X)           
                {
                    k++;  //(新增)记录障碍物的个数         
                }
            }
        }

        flag=0;  //(新增)初始状态为false;

        if(N*M-k-1>=T)       //(新增)T+k+1(起点S的位置)必须 <=   N*M(总的格子数)
        {
            dfs(sx,sy,0);
        }

        if(flag)
        {
            cout<<"YES\n";
        }
        else
        {
            cout<<"NO\n";
        }

    }
}

 

走迷宫(三):在XX限制条件下,是否走得出。