1726: 迷宫
时间限制: 1 Sec 内存限制: 128 MB提交: 1043 解决: 155
[提交][状态][讨论版][命题人:admin]
题目描述
在很多 RPG (Role-playing Games) 游戏中，迷宫往往是非常复杂的游戏环节。通常来说，我们在走迷宫的时候都需要花非常多的时间来尝试不同的路径。但如果有了算法和计算机的帮助，我们能不能有更快的方式来解决这个问题？我们可以进行一些尝试。
现在我们有一个 N 行 M 列的迷宫。迷宫的每个格子如果是空地则可以站人，如果是障碍则不行。在一个格子上，我们可以一步移动到它相邻的 8 个空地上，但不能离开地图的边界或者跨过两个障碍的夹缝。下图是一个移动规则的示例。
为了离开迷宫，我们还需要触发迷宫中所有的机关。迷宫里总共有 K 个机关，每个机关都落在一个不同的空地上。如果我们到达了某个机关所在的格子时，这个机关就会被自动触发，并在触发之后立即消失。我们的目标是按顺序触发所有的 K 个机关，而当最后一个机关被触发时，我们就可以离开迷宫了。
现在我们已经拿到了迷宫地图，并且知道所有障碍、机关的位置。初始时我们位于迷宫的某个非障碍格子上，请你计算我们最少需要移动多少步才能离开迷宫？
输入
输入的第一行是测试数据的组数 T (T ≤ 20)。
对于每组测试数据：第一行包含地图的行数 N (2 ≤ N ≤ 100)，列数 M(2 ≤ M ≤ 100) 和机关的数量 K(1 ≤ K ≤10)。接下来 N 行，每行包含 M 个字符，其中字符 ‘#’ 表示障碍，而 ‘.’ 表示空地。接下来一行描述了我们的初始位置 (x, y)，表示我们一开始在第 x 行第 y 列的格子上。这个格子保证是个空地。接下来 K 行，每行给出了一个机关的位置。所有的机关都不会出现在障碍上，并且任意两个机关不会出现在同一个空地上。我们需要按输入给定的顺序触发所有的 K 个机关。
输出
对于每组测试数据，输出离开迷宫所需要的最少步数。如果无论如何都不能离开迷宫，输出 -1。
样例输入
3 3 3 2 ... ... ... 1 1 1 3 2 2 3 3 1 ... .#. ... 1 1 3 3 2 3 1 ..# .#. 1 1 2 3
样例输出
3 3 -1
#include <iostream> #include <cstring> #include <queue> using namespace std ; #define maxn 110 int n , m , k ; char map[maxn][maxn] ; bool visit[maxn][maxn] ; int dirx[8] = {-1 , -1 , 1 , 1 , 0 , 0 , -1 , 1 } ; int diry[8] = {-1 , 1 , -1 , 1 , -1 , 1 , 0 , 0 } ; bool flag ; int result ; struct node{ int x , y ; int step ; } ; node trap[20] ; bool check(node ch , node pre){ if(1 <= ch.x && ch.x <= n && 1 <= ch.y && ch.y <= m ){ // 没有访问过，不是陷阱，不是墙壁 if(visit[ch.x][ch.y] == false && map[ch.x][ch.y] == '.'){ // 对角线移动 if(abs(ch.x - pre.x) + abs(ch.y - pre.y) == 2){ if(map[pre.x][ch.y] == '#' && map[ch.x][pre.y] == '#'){ return false ; }else { return true ; } }else{ // 直线移动 return true ; } } } return false ; } void BFS(node s , node e){ bool flag11 = false ; memset(visit , false , sizeof(visit)) ; queue<node> Q ; visit[s.x][s.y] = true ; Q.push(s) ; node q ; while(!Q.empty()){ q = Q.front() ; Q.pop() ; if(q.x == e.x && q.y == e.y){ result += q.step ; flag11 = true ; break ; } node turn ; for(int i=0 ; i<8 ; i++){ turn.x = q.x + dirx[i] ; turn.y = q.y + diry[i] ; turn.step = q.step + 1 ; if(check(turn , q )){ visit[turn.x][turn.y] = true ; Q.push(turn) ; } } } // 本次查询未找到目的地 if(flag11 == false) flag = false ; return; } int main(){ int T ; cin >> T ; while(T--){ cin >> n >> m >> k ; flag = true ; result = 0 ; for(int i=1 ; i<=n ; i ++){ for(int j=1 ; j<=m ; j++){ cin >> map[i][j] ; } } int startx , starty ; cin >> startx >> starty ; trap[0].x = startx , trap[0].y = starty ; /* * 坑点：起点可以是陷阱位置，但是不可以是第一个陷阱之后的陷阱 * 如果是第一个陷阱之后的陷阱，会导致陷阱提前触发 * 无法完成顺序触发陷阱的任务 */ for(int i=1 ; i<=k ; i++){ cin >> trap[i].x >> trap[i].y ; if(trap[i].x == startx && trap[i].y == starty && i != 1){ flag = false ; } } // 设置陷阱记号 for(int i=1 ; i<=k ; i++){ map[trap[i].x][trap[i].y] = '!' ; } for(int i=1 ; i<=k ; i++){ // 出现陷阱提前触发 或者没有到达目标地点 if(flag == false){ break ; } node s , e ; s.x = trap[i-1].x ; s.y = trap[i-1].y ; s.step = 0 ; e.x = trap[i].x ; e.y = trap[i].y ; // 取消陷阱标记 map[trap[i].x][trap[i].y] = '.' ; BFS(s , e ) ; } if(flag==false){ cout << -1 << endl ; }else{ cout << result << endl ; } } return 0 ; }