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

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdio>
 4 #include <queue>
 5 using namespace std;
 6 
 7 int n , m  , k;
 8 int sx , sy ,ex , ey ;
 9 char map[110][110] ;
10 bool v[110][110] ;
11 
12 struct node
13 {
14     int x ;
15     int y ;
16     int t ;  //当前转弯次数
17 };
18 
19 int dx[] = {1,-1,0,0} ;
20 int dy[] = {0,0,1,-1} ;
21 
22 int bfs()
23 {
24     queue<node> q ;
25     node now , temp ;
26     now.x = sx ;
27     now.y = sy ;
28     now.t = -1 ;
29     memset(v , 0 , sizeof(v)) ;
30     v[sx][sy] = 1 ;
31     q.push(now) ;
32     while(!q.empty())
33     {
34         now = q.front() ;
35         q.pop() ;
36         if (now.t >= k) //如果还没走到终点 转弯次数已经用完了 就不用再往下走了
37             continue ;
38         for (int i = 0 ; i < 4 ; i++)
39         {
40             temp.x = now.x + dx[i] ;
41             temp.y = now.y + dy[i] ;
42             temp.t = now.t + 1 ;
43             while(1)
44             {
45                 if (temp.x<0 ||temp.y<0 || temp.x>= n || temp.y>= m || map[temp.x][temp.y] == '*')
46                     break ;
47                 if (temp.x == ex && temp.y == ey)
48                     return 1 ;
49                 if (!v[temp.x][temp.y])
50                 {
51                     q.push(temp) ;
52                     v[temp.x][temp.y] = 1 ;
53                 }
54                 temp.x += dx[i] ;
55                 temp.y += dy[i] ;
56             }
57         }
58     }
59     return 0 ;
60 }
61 
62 int main ()
63 {
64     //freopen("in.txt","r",stdin) ;
65     int T ;
66     scanf("%d" , &T) ;
67     while (T--)
68     {
69          scanf("%d %d" , &n , &m) ;
70          for (int i = 0 ; i < n ; i++)
71             for (int j = 0 ; j < m ; j++)
72          {
73              cin>>map[i][j] ;
74          }
75          scanf("%d%d%d%d%d" , &k , &sy , &sx , &ey , &ex) ;
76          sy-- ;
77          sx-- ;
78          ey-- ;
79          ex-- ;
80          if (bfs())
81             printf("yes
") ;
82          else
83             printf("no
") ;
84 
85     }
86 
87     return 0 ;
88 }

View Code

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

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