HDU 1728 逃离迷宫

 1 #include<iostream>
 2 #include<queue>
 3 using namespace std;
 4 #define maxn 105
 5 char maze[maxn][maxn];
 6 int dir[][2] = {{0,-1},{1,0},{0,1},{-1,0}};
 7 int visited[maxn][maxn];
 8 int m,n,k,si,sj,ei,ej;
 9 bool ok(int i,int j)
10 {
11     if(i>= 0 && i <m && j >= 0 && j < n && maze[i][j] != ‘*‘)
12         return true;
13     return false;
14 }
15 struct node
16 {
17     int x,y;
18 };
19 void BFS()
20 {
21     queue<node> q;
22     memset(visited,-1,sizeof(visited));
23     node temp,next;
24     temp.x = si,temp.y = sj;
25     q.push(temp);
26     while(!q.empty())
27     {
28         temp = q.front();
29         q.pop();
30         int times = visited[temp.x][temp.y]+1;  //之前找到temp的方向的点都已被找过，所以接下来的方向与之前找到temp的方向不同，所以拐弯了，需+1
31         for(int i = 0; i < 4; i++)
32         {
33             next.x = temp.x+dir[i][0],next.y = temp.y+dir[i][1];
34             while(ok(next.x,next.y))
35             {
36                 if(visited[next.x][next.y] == -1)   //此点从没被找过
37                 {
38                     if(next.x == ei && next.y == ej && times <= k)
39                     {
40                         printf("yes\n");
41                         return;
42                     }
43                     q.push(next),visited[next.x][next.y] = times;
44                 }
45                 next.x += dir[i][0],next.y += dir[i][1];
46             }
47         }
48     }
49     printf("no\n");
50 }
51 int main()
52 {
53     //freopen("1728.txt","r",stdin);
54     int t;
55     scanf("%d",&t);
56     while(t--)
57     {
58         int i,j;
59         scanf("%d%d",&m,&n);
60         for(i = 0; i < m; i++)
61             for(j = 0; j < n; j++)
62                 cin >> maze[i][j];
63             //scanf("%s",maze[i]);
64         scanf("%d%d%d%d%d",&k,&sj,&si,&ej,&ei);
65         si--,sj--,ei--,ej--;//为了与坐标对应
66         BFS();
67     }
68     return 0;
69 }