hdu 1728 迷宫 给定最大转弯次数 (BFS)

给出起点 终点 以及转弯次数 在<=转弯次数的条件 能否走到终点

Sample Input
2
5 5
...** // .可走 *不可走
*.**.
.....
.....
*....
1 1 1 1 3 //最大转弯次数 起始y 起始x ....
5 5
...**
*.**.
.....
.....
*....
2 1 1 1 3

Sample Output
no
yes

 #include <iostream>

 #include <cstring>

 #include <cstdio>

 #include <queue>

 using namespace std;

 int n , m  , k;

 int sx , sy ,ex , ey ;

 char map[][] ;

 bool v[][] ;

 struct node

 {

     int x ;

     int y ;

     int t ;  //当前转弯次数

 };

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

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

 int bfs()

 {

     queue<node> q ;

     node now , temp ;

     now.x = sx ;

     now.y = sy ;

     now.t = - ;

     memset(v ,  , sizeof(v)) ;

     v[sx][sy] =  ;

     q.push(now) ;

     while(!q.empty())

     {

         now = q.front() ;

         q.pop() ;

         if (now.t >= k) //如果还没走到终点 转弯次数已经用完了 就不用再往下走了

             continue ;

         for (int i =  ; i <  ; i++)

         {

             temp.x = now.x + dx[i] ;

             temp.y = now.y + dy[i] ;

             temp.t = now.t +  ;

             while()

             {

                 if (temp.x< ||temp.y< || temp.x>= n || temp.y>= m || map[temp.x][temp.y] == '*')

                     break ;

                 if (temp.x == ex && temp.y == ey)

                     return  ;

                 if (!v[temp.x][temp.y])

                 {

                     q.push(temp) ;

                     v[temp.x][temp.y] =  ;

                 }

                 temp.x += dx[i] ;

                 temp.y += dy[i] ;

             }

         }

     }

     return  ;

 }

 int main ()

 {

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

     int T ;

     scanf("%d" , &T) ;

     while (T--)

     {

          scanf("%d %d" , &n , &m) ;

          for (int i =  ; i < n ; i++)

             for (int j =  ; j < m ; j++)

          {

              cin>>map[i][j] ;

          }

          scanf("%d%d%d%d%d" , &k , &sy , &sx , &ey , &ex) ;

          sy-- ;

          sx-- ;

          ey-- ;

          ex-- ;

          if (bfs())

             printf("yes\n") ;

          else

             printf("no\n") ;

     }

     return  ;

 }