1726 : 迷宫 (广搜)
  anLrwkgbyYZS 2023年12月30日 8 0


题目链接:点击打开链接

题目描述 :

在很多 RPG (Role-playing Games) 游戏中,迷宫往往是非常复杂的游戏环节。通常来说,我们在走迷宫的时候都需要花非常多的时间来尝试不同的路径。但如果有了算法和计算机的帮助,我们能不能有更快的方式来解决这个问题?我们可以进行一些尝试。

现在我们有一个 N 行 M 列的迷宫。迷宫的每个格子如果是空地则可以站人,如果是障碍则不行。在一个格子上,我们可以一步移动到它相邻的 8 个空地上,但不能离开地图的边界或者跨过两个障碍的夹缝。下图是一个移动规则的示例。

1726 : 迷宫 (广搜)_#include

为了离开迷宫,我们还需要触发迷宫中所有的机关。迷宫里总共有 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

 

注意:如果我们到达了某个机关所在的格子时,这个机关就会被自动触发,并在触发之后立即消失。

你如果去找第i个机关 踩到i之后任何一个机关,都会失败

出生在除了第一个机关外任何一个机关,失败

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
 
using namespace std;
 
const int N = 110;
 
char a[N][N]; // 存储地图 
int vis[N][N]; // vis[i][j] = 1 该点已经遍历过 为 0 则未遍历过 
int mis[N][N]; // mis[i][j] = 1 该点有以后要触发机关,现在不能遍历  
 
typedef struct point {
   int x, y, step;
}P;
 
int n, m, k;

// 8 个 方向 
int road[8][2] = {-1,-1, -1,0, -1,1,
                  0,-1, 0, 1,
                  1,-1, 1,0, 1,1}; 
 
queue <P> Q;
P score[N];
 
// 判断 tem 是否在图外 
bool judge(P tem) {
   if(tem.x < 0 || tem.x >= n || tem.y < 0 || tem.y >= m)
       return false;
   return  true;
}
 
// 判断斜着走到 tem 是否可以 
bool wtwalk(int i, P tem) {
   P tem1, tem2;
   tem1 = tem;
   tem2 = tem;
 
   if(i == 0) {
      tem1.y ++;
      tem2.x ++;
   }
   else if(i == 2) {
      tem1.y --;
      tem2.x ++;
   }
   else if(i == 5) {
      tem1.x --;
      tem2.y ++;
   }
   else {
      tem1.x--;
      tem2.y--;
   }
 
   if(a[tem1.x][tem1.y] == '#' && a[tem2.x][tem2.y] == '#')
      return false;
   return true;
}

// bfs Sta为起点 , End为终点
// 如果可以到达终点 , 返回步数
// 如果不能返回 -1 
int bfs(P Sta, P End) {
    memset(vis, 0, sizeof(vis));
    vis[Sta.x][Sta.y] = 1;
    while(!Q.empty()) Q.pop();
    Q.push( Sta );
 
    P now, tem;
    while( !Q.empty() ) {
        now = Q.front();
        if(now.x == End.x && now.y == End.y) {
            return now.step;
        }
        Q.pop();
 
        for(int i=0; i<8; i++) {
            tem.x = now.x + road[i][0];
            tem.y = now.y + road[i][1];
 
            if( vis[tem.x][tem.y] || mis[tem.x][tem.y] || a[tem.x][tem.y] == '#' || !judge(tem) )
                continue;
 
            if(0 == i || 2 == i || 5 == i || 7 == i) {
                if(!wtwalk(i, tem))
                    continue;
            }
        //   cout << tem.x+1 << " " << tem.y+1 << endl;
            vis[tem.x][tem.y] = 1;
            tem.step = now.step+1;
            Q.push( tem );
        }
    }
    return -1;
}
int main()
{
     int T;
     cin >> T;
     for(int t=1; t<=T; t++) {
          cin >> n >> m >> k;
          memset(mis, 0, sizeof(mis));
 
          for(int i=0; i<n; i++)
              cin >> a[i];
 
          P now;
          cin >> now.x >> now.y;
          now.x --, now.y --;
          now.step = 0;
 
          int ans = 0;
          for(int i=1; i<=k; i++) {
             cin >> score[i].x >> score[i].y;
             score[i].x --;
             score[i].y --;
             if(score[i].x == now.x && score[i].y == now.y && i!=1){
                 ans = -1;
             }
             if(i != 1) {
                mis[score[i].x][score[i].y] = 1;
             }
          }
          if(ans == -1) {
            cout << "-1" << endl;
            continue;
          }
 
          for(int i=1; i<=k; i++) {
 
             mis[score[i].x][score[i].y] = 0;
             int temp = bfs(now, score[i]);
 
             if(temp >= 0) {
                score[i].step = 0;
                now = score[i];
                ans += temp;
             }
             else {
                ans = -1;
                break;
             }
          }
          cout << ans << endl;
     }
     return 0;
}

 

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年12月30日 0

暂无评论

anLrwkgbyYZS