迷宫连通性判断

2021年09月15日 阅读数:1
这篇文章主要向大家介绍迷宫连通性判断,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。
时间限制: 3 Sec   内存限制: 128 MB 难度:Easy
题目描述

小明最近沉迷于一个游戏,可是他在玩游戏中常常遇到各类各样的迷宫,其中既有走得通的迷宫也有走不通的迷宫。php

小明懒得费这个力,想让你帮忙写一个程序帮他一劳永逸地解出全部的迷宫。ios

输入

第一行输入一个正整数n,表明待求解的迷宫的数量。ide

其后n组数据,每组数据输入一个数m,表明迷宫的长度和宽度。函数

其后输入m行,m列的一个矩阵,其中0表明此格有障碍,不能通行,1表明能够经过。优化

数据保证最左上角和最右下角的格子不会有障碍。spa

迷宫不会大于30x30。code

输出

判断每一个迷宫是否能从左上角的起点走到右下角的终点,每一个迷宫输出“YES”或“NO”表明这个迷宫是否能够走通。递归

样例输入

2
3
1 1 0
0 1 1
0 0 1
4
1 1 0 1
0 0 1 1
1 1 0 1
1 1 0 1

样例输出

YES
NO

 

提示

使用C++语言解决问题,比Java、JS快数倍。游戏

来源

基础题-模拟类问题 进程

分析

这道题是初级迷宫问题,只要求连通性,不须要求最短路径,仍是比较简单的,解题方法是穷举法:穷尽每一条路,直到终点为止。但走过的路就没必要再走一遍了,因此走过的地方就变成了路障:咱们用bool矩阵存储全部的格子,0表示路障,1表示还未走过的地方,咱们递归的目的就是让全部走过的1变成0,途中遇到终点则提早结束。每次递归向上下左右4个方向尝试着走一格,每走一步都要进行如下4个判断:

  • 是否有路障?结束函数

  • 是否走过了?结束函数

  • 是否越界?结束函数

  • 到达终点了嘛?结束程序

其中前两种判断咱们优化成一种了,剩下3个判断,若是经过了这3个判断,则成功地走到了这个格子,而后这个格子置0,接着再向四个方向走。而后有2种状况:要么走完了全部格子,则走不通,要么中间遇到终点,走通了。

提早结束递归

遇到终点则能够结束程序输出“YES”了,但怎么结束呢?固然能够调用方法结束进程,但若是后面还有活要作,则须要结束当前的递归栈,也就是第一次调用递归函数的地方,return只能结束当前函数,但当前函数已是递归的第n层栈了,下面还有好多父函数,如何直接结束至栈底呢?思来想去C++里只有throw能实现这个功能,同时还要在栈底进行捕获,彷佛JavaScript也只能抛出异常:https://stackoverflow.com/a/13637203/8047150

优先向终点方向走

题目中,终点在右下角,为了更快地到达终点,每次的4次递归优先走右下,再走左上,这样到达终点的时间更短一些。品尝下面的代码:

代码

#include <iostream>
using namespace std;
 
// 迷宫边长
int n;
 
bool map[30][30] = {0};
 
int go(int x, int y){
    // 不可走?
    if (map[x][y] == false)
        return 0;
    // 是否越界
    if (x < 0 || y < 0 || x >= n || y >= n)
        return 0;
 
    // 到达终点?
    if (x == n - 1 && y == n - 1)
        throw " ";  // 结束调用栈
 
    // 已走过,置0
    map[x][y] = false;
 
    go(x + 1, y);  // 下
    go(x, y + 1);  // 右
    go(x - 1, y);  // 上
    go(x, y - 1);  // 左
 
    return 0;
}
 
int main(){
    // 迷宫数量
    int k;
    cin >> k;
    for (int u = 0; u < k; ++u){
        cin >> n;
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                cin >> map[i][j];
        try{
            // 从起点开始递归
            go(0, 0);
            cout << "NO" << endl;  // 全走完了,没遇到终点
        }
        catch (...){
            cout << "YES" << endl;  // 遇到终点啦
        }
    }
    return 0;
}
/**************************************************************
    Problem: 3844
    User: jim
    Language: C++
    Result: 正确
    Time:4 ms
    Memory:2320 kb
****************************************************************/