ACM 广搜 Hero In Maze

曾经终败给现在 2022-07-12 02:15 145阅读 0赞

这是Hero In Maze三道题，分别是TOJ中Hero In Maze简单版，普通版，提高版。

以下我将一一阐述。

**TOJ 2777 Hero In Maze简单版**

描述

500年前，Jesse是我国最卓越的剑客。他英俊潇洒，而且机智过人^\_^。

突然有一天，Jesse心爱的公主被魔王困在了一个巨大的迷宫中。Jesse听说这个消息已经是两天以后了，他急忙赶到迷宫，开始到处寻找公主的下落。

请你判断他是否能救出心爱的公主。(假设有路可以通到公主那就可以找到公主)。

输入

题目包括多组测试数据。  
每组测试数据以两个整数n,m(0<n, m≤20)开头，分别代表迷宫的长和高。紧接着有m行，n列字符，由"."，"\*"，"P"，"S"组成。其中  
"." 代表能够行走的空地。  
"\*" 代表墙壁，Jesse不能从此通过。  
"P" 是公主所在的位置。  
"S" 是Jesse的起始位置。  
Jesse只能选择上、下、左、右任意一方向走一步。  
输入以0 0结束。

输出

如果能救出公主输出YES，否则输出NO。

样例输入

4 4 .... .... .... S\*\*P 4 4 .... .... \*\*\*\* S\*\*P 0 0

样例输出

YES NO

这个用深搜就可以，直接判断能不能从S走到P即可。

#include <stdio.h>
    int a,b,s,k=0;
    char m[21][21];	
    int dir[4][2]={1,0,0,1,-1,0,0,-1};
    void dfs(int x,int y)
    {  
       if(m[x][y]=='P')
       k=1;
    	m[x][y]='*';
    	int i,xx,yy;
       for(i=0;i<4;i++)
       {
       	xx=x+dir[i][0];
       	yy=y+dir[i][1];
       	if(xx>=0&&xx<a&&yy>=0&&yy<b&&m[xx][yy]!='*')
        dfs(xx,yy);
       }	
    }
    int main()//2777
    {
    	int i,j,u,w;
    	while(scanf("%d%d",&a,&b))
    	{   
    	    s=0;k=0;
    		if(a==0&&b==0)break;			
    		for(i=0;i<a;i++)
    		{getchar();
    			for(j=0;j<b;j++)
    			{
    				scanf("%c",&m[i][j]);
    			   if(m[i][j]=='S')
    			    u=i,w=j;
    			}
    		} 
    		dfs(u,w);
    		if(k==0)
    		printf("NO\n");
    		else
    		printf("YES\n");
    	}
    }

**TOJ 1005 Hero In Maze**

描述

500年前，Jesse是我国最卓越的剑客。他英俊潇洒，而且机智过人^\_^。  
  
突然有一天，Jesse心爱的公主被魔王困在了一个巨大的迷宫中。Jesse听说这个消息已经是两天以后了，他知道公主在迷宫中还能坚持T天，他急忙赶到迷宫，开始到处寻找公主的下落。  
时间一点一点的过去，Jesse还是无法找到公主。最后当他找到公主的时候，美丽的公主已经死了。从此Jesse郁郁寡欢，茶饭不思，一年后追随公主而去了。T\_T  
500年后的今天，Jesse托梦给你，希望你帮他判断一下当年他是否有机会在给定的时间内找到公主。  
  
他会为你提供迷宫的地图以及所剩的时间T。请你判断他是否能救出心爱的公主。

输入

题目包括多组测试数据。  
每组测试数据以三个整数N,M,T(0<n, m≤20, t>0)开头，分别代表迷宫的长和高，以及公主能坚持的天数。  
紧接着有M行，N列字符，由"."，"\*"，"P"，"S"组成。其中  
"." 代表能够行走的空地。  
"\*" 代表墙壁，Jesse不能从此通过。  
"P" 是公主所在的位置。  
"S" 是Jesse的起始位置。  
每个时间段里Jesse只能选择“上、下、左、右”任意一方向走一步。  
输入以0 0 0结束。

输出

如果能在规定时间内救出公主输出“YES”，否则输出“NO”。

样例输入

4 4 10 .... .... .... S\*\*P 0 0 0

样例输出

YES

题目意思与上面一致，但是这题要判断时间，所以不能用深搜了，需要用广搜来计算最短时间。

这是一个大佬写的，我没看懂...

http://blog.csdn.net/j\_sure/article/details/19997869

#include <cstdio>  
    #include <iostream>  
    #include <algorithm>  
    #include <cstring>   
    #include <queue>  
    
    using namespace std;   
    int DTx[4]={-1,0,1,0};  
    int DTy[4]={0,1,0,-1};  
    char map[25][25];  
    int dp[25][25];  
    int x,y,X,Y;  
    int minn;  
    int n,m,t;  
    struct H{  
        int x,y;  
        int time;  
    };  
    int bfs(int h,int z)  
    {  
        int i,j;  
        queue <H> q;  
        H a,b,c;  
        a.x=h;  
        a.y=z;  
        a.time=0;  
        q.push(a);  
        while(!q.empty())  
        {  
            b=q.front();  
            q.pop();  
            if(b.x==X&&b.y==Y)  
                return b.time;  
            for(i=0;i<4;i++)  
            {  
                c.x=b.x+DTx[i];  
                c.y=b.y+DTy[i];  
                if(c.x>=0&&c.x<m&&c.y>=0&&c.y<n&&!dp[c.x][c.y])  
                    {  
                        dp[c.x][c.y]=1;  
                        c.time=b.time+1;  
                        q.push(c);  
                    }  
            }  
        }  
        return -1;  
    }  
    int main()  
    {  
        int i,j;  
        while(~scanf("%d%d%d",&n,&m,&t)&&(n||m||t))  
        {  
            memset(dp,0,sizeof dp);  
            for(i=0;i<m;i++)  
                cin>>map[i];  
            for(i=0;i<m;i++)  
                for(j=0;j<n;j++)  
                if(map[i][j]=='S')  
                {x=i;y=j;dp[i][j]=1;}  
                else if(map[i][j]=='P')  
                {X=i;Y=j;}  
                else if(map[i][j]=='*')  
                    dp[i][j]=1;  
            minn=bfs(x,y);   
            //printf("%d\n",minn);   
            if(minn<=t&&minn!=-1)  
            printf("YES\n");  
            else 
    	printf("NO\n");  
        }  
        return 0;  
    }

**TOJ 3305 Hero In Maze ||**

描述

500年前，Jesse是我国最卓越的剑客。他英俊潇洒，而且机智过人^\_^。  
突然有一天，Jesse心爱的公主被魔王困在了一个巨大的迷宫中。Jesse听说这个消息已经是两天以后了，他急忙赶到迷宫，开始到处寻找公主的下落。令人头痛的是，Jesse是个没什么方向感的人，因此，他在行走过程中，不能转太多弯了，否则他会晕倒的。 我们假定Jesse和公主所在的位置都是空地，初始时，Jesse所面向的方向未定，他可以选择4个方向的任何一个出发，而不算成一次转弯。希望你帮他判断一下他是否有机会找到心爱的公主。

输入

题目包括多组测试数据.

第1行为一个整数T(1 ≤ T≤ 100),表示测试数据的个数，接下来为T组测试数据.

每组测试数据以两个整数N,M,K(1<=N, M≤100, 0<K<=10)开头，分别代表迷宫的高，长和Jesse最多能转的弯数，(紧接着有N行，M列字符，由"."，"\*"，"P"，"S"组成。其中  
"." 代表能够行走的空地。  
"\*" 代表墙壁，Jesse不能从此通过。  
"P" 是公主所在的位置。  
"S" 是Jesse的起始位置。  
每个时间段里Jesse只能选择“上、下、左、右”任意一方向走一步。

输出

如果Jesse能在晕之前找到公主，输出“YES”，否则输出“NO”。

样例输入

2 5 5 1 P..\*\* \*.\*\*. S.... ..... \*.... 5 5 2 P..\*\* \*.\*\*. S.... ..... \*....

样例输出

NO YES

题目意思与上一致，就是判断条件从时间变成了转弯次数。注意初始的一次不算转弯。

判断转弯次数的话我设置了一个wan,即第一次转的方向（i）和第二次的不一样时，就是转弯了。

然后我写的广搜TOJ没AC，但是我感觉完美了...先放上来吧~

#include <cstdio>  
    #include <iostream>  
    #include <algorithm>  
    #include <cstring>  
    #include <cmath>  
    #include <queue>
    using namespace std;   
    int DTx[4]={-1,0,1,0};  
    int DTy[4]={0,1,0,-1};  
    char map[101][101];  
    int dp[101][101];  
    int x,y,X,Y;  
    int minn;  
    int n,m,t;  
    struct H{  
        int x,y;  
        int time,wan;  
    };  
    int bfs(int h,int z)  
    {  
        int i,j;  
        queue <H> q;  
        H a,b,c;  
        a.x=h;  
        a.y=z;  
        a.time=-1; 
    	a.wan=-1; 
        q.push(a);  
        while(!q.empty())  
        {  
            b=q.front();  
            q.pop();  
            if(b.x==X&&b.y==Y)  
                return b.time;  
            for(i=0;i<4;i++)  
            {  
                c.x=b.x+DTx[i];  
                c.y=b.y+DTy[i];  
                c.wan=i;
                if(c.x>=0&&c.x<m&&c.y>=0&&c.y<n&&!dp[c.x][c.y])  
                    {  
                        dp[c.x][c.y]=1;  
                        if(c.wan!=b.wan)//若两次方向一样，则没有转弯。 
                        c.time=b.time+1; 
    					q.push(c); 
                    }  
            }  
        }  
        return -1;  
    }  
    int main()  
    {  
        int i,j,o;  
        scanf("%d",&o);
        while(o--)  
        {  
    		scanf("%d%d%d",&m,&n,&t); 
            memset(dp,0,sizeof dp);  
            for(i=0;i<m;i++)  
                cin>>map[i];  
            for(i=0;i<m;i++)  
                for(j=0;j<n;j++)  
                if(map[i][j]=='S')  
                {x=i;y=j;dp[i][j]=1;}  
                else if(map[i][j]=='P')  
                {X=i;Y=j;}  
                else if(map[i][j]=='*')  
                    dp[i][j]=1;  
            minn=bfs(x,y);   
            //printf("%d\n",minn);   
            if(minn<=t&&minn!=-1)  
            printf("YES\n");  
            else 
    		printf("NO\n");  
        }  
        return 0;  
    }

然后下面的是童冰学姐写的深搜，简单很多。

#include<stdio.h>
    int n,m,b[4][2]={
       {0,1},{0,-1},{1,0},{-1,0}},s,k;
    char a[101][101];
    void dfs(int x,int y,int r,int w)
    {
        if(k==1)return;
        int i,x0,y0,r0;
        if(x<0||y<0||x>=n||y>=m||r>s+1||a[x][y]=='*')return;
        if(a[x][y]=='P')
    	{k=1;return;}
        a[x][y]='*';
        for(i=0;i<4;i++)
        {
            x0=x+b[i][0];
            y0=y+b[i][1];
            if(w!=i)
            r0=r+1;
            else r0=r;
            dfs(x0,y0,r0,i);
        }
        a[x][y]='.';
    }
    int main()
    {
        int i,j,x0,y0,t;
        scanf("%d",&t);
        while(t--)
        {
            k=0;
            scanf("%d%d%d",&n,&m,&s);
            for(i=0;i<n;i++)
            {
            	scanf("%s",a[i]);
            	for(j=0;j<m;j++)
            	{
                	if(a[i][j]=='S')
                	x0=i,y0=j;
            	}
    		}
            dfs(x0,y0,0,-1);
            if(k)printf("YES\n");
            else printf("NO\n");
        }
    }