广搜

2019-11-17

广度优先搜索

Breadth First Search，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。是一种用于图的查找算法，可帮助回答两类问题:

第一类问题: 从节点A出发，前往节点B的路径

第二类问题: 从节点A出发，前往节点B的哪条路径最短

1005: Hero In Maze

时间限制(普通/Java):1000MS/10000MS 内存限制:65536KByte 总提交: 5700 测试通过:1360

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

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
char gra[25][25];			 //地图
bool vis[25][25]={0};                     //判断点是否走过
int dir[4][2]={-1,0,0,-1,1,0,0,1};        //走的方向
int m,n,t,step;
int sy,sx;
struct point{
    int x,y,s;                            //坐标，步长
};
bool BFS(){
    queue<point> qu;                      
    vis[sx][sy]=1;
    qu.push({sx,sy,0});                  //队列初始化
    while(!qu.empty())
    {
        int y=qu.front().y,x=qu.front().x,s=qu.front().s;  //返回队列的第一个元素
        if(gra[x][y]=='P')
        {
            return s<=step;
        }

        for(int i=0;i<4;i++)
        {
            sy=y+dir[i][0];
            sx=x+dir[i][1];

            if(sx<n && sx>=0 && sy<m && sy>=0
               && !vis[sx][sy] && gra[sx][sy]!='*')   //在图内，未走过,且不为'*'
            {

                vis[sx][sy]=1;
                qu.push({sx,sy,s+1});           //入队，并且步长+1
                 //printf("%d %d %d\n",sx,sy,s);
            }
        }
        qu.pop();                               //出队
    }
    return 0;
}
int main()
{
    while(scanf("%d%d%d",&m,&n,&step),m || n || step)
    {
        memset(vis,0,sizeof(vis));         //初始化vis
        for(int i=0;i<n;i++)
        {
            getchar();
            for(int j=0;j<m;j++)
            {
                gra[i][j]=getchar();
                if(gra[i][j]=='S')sx=i,sy=j;
            }
        }
        bool f=BFS();
        printf("%s\n",f? "YES" : "NO");
    }
    return 0;
}