hdu1728 逃离迷宫bfs

题目链接：http://icpc.njust.edu.cn/Problem/Hdu/1728/

关于广度优先搜索的第一篇题解。广度优先搜索，就是状态树的层次遍历，一层一层的搜索，直到搜索到目标状态为止。在扩展的过程中设定一种由上一层扩展到下一层的转化机制，将出现的新的状态放入队列之中，每次取出队首元素，大部分情况下bfs是用来搜索最优值的问题，优先队列的作用就是一旦搜索到目标状态，跟随的结果状态一定是最优的。为了避免重复相同的搜索，可设置访问记录。一般运用队列这种数据结构，使得最初搜索的状态在前，可以继续下一次搜索。

题目意思：给出地图，要求判断在最多k次转弯的条件下是否能够从一点都到另一点。写完记得检查变量的初始化。

代码如下：

 #include<bits/stdc++.h>

 using namespace std;

 typedef unsigned int ui;

 typedef long long ll;

 typedef unsigned long long ull;

 #define pf printf

 #define mem(a,b) memset(a,b,sizeof(a))

 #define prime1 1e9+7

 #define prime2 1e9+9

 #define pi 3.14159265

 #define lson l,mid,rt<<1

 #define rson mid+1,r,rt<<1|1

 #define scand(x) scanf("%llf",&x)

 #define f(i,a,b) for(int i=a;i<=b;i++)

 #define scan(a) scanf("%d",&a)

 #define dbg(args) cout<<#args<<":"<<args<<endl;

 #define inf 0x3f3f3f3f

 #define maxn 105

 #define maxm 2000010

 int n,m,t,k;

 int Map[maxn][maxn];

 int sx,sy,tx,ty;

 bool flag=false,vis[maxn][maxn];

 int dir[][]={,,,-,,,-,};

 struct node{

     int x,y;

     int step;

     node(int x,int y,int step):x(x),y(y),step(step){};

     node(){};

 };

 node cur,nxt;

 void bfs()

 {

     queue<node>q;

     node st(sx,sy,-);

     q.push(st);

     vis[sx][sy]=true;//标记该状态已经访问过

     while(!q.empty())

     {

         cur=q.front();//获取队首结点

         q.pop();//队首状态弹出

         if(cur.x==tx&&cur.y==ty&&cur.step<=k)

         {

         //    dbg(cur.step);

             flag=true;

             return;

         }

         f(i,,)

         {

             nxt=cur;

             nxt.x+=dir[i][];

             nxt.y+=dir[i][];

             while(nxt.x>=&&nxt.x<n&&nxt.y>=&&nxt.y<m&&Map[nxt.x][nxt.y])//检查是否越界、可走

             {

                 if(!vis[nxt.x][nxt.y])//只要没有访问过，那一定是经过转弯了的，我们设定一次朝着一个方向一直走到底

                 {

                     vis[nxt.x][nxt.y]=true;

                     nxt.step=cur.step+;

                     q.push(nxt);//合法状态入队

                 }

                 nxt.x+=dir[i][];

                 nxt.y+=dir[i][];//继续朝同一个方向走到底，这个方向上的step都是同一个值

             }

         }

     }

 }

 int main()

 {

     //freopen("input.txt","r",stdin);

     //freopen("output.txt","w",stdout);

     std::ios::sync_with_stdio(false);

     scan(t);

     while(t--)

     {

         flag=false;

         scan(n);

         scan(m);

         mem(Map,);

         mem(vis,false);

         char c;

         f(i,,n-)

             f(j,,m-)

             {

                 scanf(" %c",&c);

                 if(c=='.')Map[i][j]=;

             }

             scanf("%d%d%d%d%d",&k,&sy,&sx,&ty,&tx);//注意数据的读入，行列不可错

             sx--,sy--,tx--,ty--;

             bfs();

             if(flag)pf("yes\n");

             else pf("no\n");

      }

  }

巴特西

hdu1728 逃离迷宫bfs

最新文章

热门文章