文档章节

1726: 迷宫(BFS(有坑点))

o
 osc_z1hvg4cu
发布于 2018/04/24 21:31
字数 1151
阅读 0
收藏 0

精选30+云产品,助力企业轻松上云!>>>

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 ; 
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

Springboot+Redis综合运用/缓存使用

项目引入依赖(安装redis自行百度) <!-- spring-boot redis --><dependency> <groupId>org.springframework.boot</groupId> <artifactId>spring-boot-starter-data-redis</artifactI......

心田已荒
37分钟前
5
0
puppeteer csdn 登录 [失败, 跨域cookie无法解决]

使用 puppeteer 登录csdn 暂时没能解决这个问题 滑块可以滑到右边 原因在于cookie const puppeteer = require('puppeteer');const uid = '===';const pwd = '===';(async () => { ......

阿豪boy
56分钟前
17
0
即使使用__init__.py,也如何解决“尝试以非软件包方式进行相对导入”

问题: I'm trying to follow PEP 328 , with the following directory structure: 我正在尝试使用以下目录结构来遵循PEP 328 : pkg/ __init__.py components/ core.py __init_......

富含淀粉
56分钟前
19
0
Java线程池

前言 Java中对线程池的抽象是ThreadPoolExecutor类,Executors是一个工具类,内置了多种创建线程池的方法: newFixedThreadPool:固定长度线程池 newCachedThreadPool :可缓存线程池 newSin...

nullpointerxyz
今天
57
0
Python笔记:用Python制作二维码

这些年,二维码在我国的日常使用频率特别大。因为其具有简单及安全性吧!除了用网络工具制作二维码,其实用JavaScript或Python也可以制作二维码,而且更有个性。 示例一(制作普通黑白二维码...

tengyulong
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部