HDU 1728 逃离迷宫

【题目描述 - Problem Description】

　　给定一个m × n (m行, n列)的迷宫，迷宫中有两个位置，gloria想从迷宫的一个位置走到另外一个位置，当然迷宫中有些地方是空地，gloria可以穿越，有些地方是障碍，她必须绕行，从迷宫的一个位置，只能走到与它相邻的4个位置中,当然在行走过程中，gloria不能走到迷宫外面去。令人头痛的是，gloria是个没什么方向感的人，因此，她在行走过程中，不能转太多弯了，否则她会晕倒的。我们假定给定的两个位置都是空地，初始时，gloria所面向的方向未定，她可以选择4个方向的任何一个出发，而不算成一次转弯。gloria能从一个位置走到另外一个位置吗？

【输入 - Input】

【输出 - Output】

　　第1行为一个整数t (1 ≤ t ≤ 100),表示测试数据的个数，接下来为t组测试数据，每组测试数据中，
　　第1行为两个整数m, n (1 ≤ m, n ≤ 100),分别表示迷宫的行数和列数，接下来m行，每行包括n个字符，其中字符'.'表示该位置为空地，字符'*'表示该位置为障碍，输入数据中只有这两种字符，每组测试数据的最后一行为5个整数k, x₁, y₁, x₂, y₂ (1 ≤ k ≤ 10, 1 ≤ x₁, x₂ ≤ n, 1 ≤ y₁, y₂ ≤ m),其中k表示gloria最多能转的弯数，(x₁, y₁), (x₂, y₂)表示两个位置，其中x₁，x₂对应列，y₁, y₂对应行。

　　每组测试数据对应为一行，若gloria能从一个位置走到另外一个位置，输出“yes”，否则输出“no”。

【输入样例 - Sample Input】	【输出样例 - Sample Output】
2 5 5 ...** .. ..... ..... .... 1 1 1 1 3 5 5 ...** .. ..... ..... .... 2 1 1 1 3	no yes

【题解】

　　因为自己这方面只会DFS和SPFA，据说这道题是BFS，而且BFS和SPFA同源？所以就来试试

　　把起点标记为-1，周围4个方向能刷新则无脑刷新成0，保存被刷新的点进队列，以此类推……

　　当前点的数值达到K的时候就可以停止刷新了，因为前面刷新的值都<=k，后面没必要继续了。

【代码 C++】

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<queue>
 4 char map[105][105];
 5 int k;
 6 struct point{
 7     int x, y;
 8 }temp;
 9 std::queue<point> que;
10 void mark(int nowX, int nowY, int fX, int fY){
11     int len = map[nowY][nowX] + 1;
12     while (map[nowY + fY][nowX + fX] != '*' && len <= map[nowY + fY][nowX + fX]){
13         nowY += fY, nowX += fX, map[nowY][nowX] = len;
14         temp.y = nowY, temp.x = nowX, que.push(temp);
15     }
16 }
17 int main(){
18     int t, stX, stY, edX, edY, lX, lY, i;
19     scanf("%d", &t);
20     memset(map, '*', sizeof(map));
21     while (t--){
22         scanf("%d%d", &lY, &lX), getchar();
23         ++lX;
24         for (i = 1; i <= lY; ++i) gets(&map[i][1]), map[i][lX] = '*';
25         memset(map[i], '*', sizeof(map[i]));
26         scanf("%d%d%d%d%d", &k, &stX, &stY, &edX, &edY);
27         while (!que.empty()) que.pop();
28         if (map[stY][stX] != '*'){
29             map[stY][stX] = -1;
30             temp.x = stX, temp.y = stY, que.push(temp);
31         }
32         while (!que.empty()){
33             temp = que.front(), stX = temp.x, stY = temp.y;
34             if (map[stY][stX] >= k) break;
35             mark(stX, stY, 0, 1);
36             mark(stX, stY, 0, -1);
37             mark(stX, stY, 1, 0);
38             mark(stX, stY, -1, 0);
39             que.pop();
40         }
41         if (map[edY][edX] <= k) puts("yes");
42         else puts("no");
43     }
44     return 0;
45 }

HDU 1728