迷宫连通性判断

原创
2021/08/28 20:13
阅读数 31

时间限制: 3 Sec  
内存限制: 128 MB
难度:Easy



题目描述


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

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


输入

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

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

其后输入m行,m列的一个矩阵,其中0代表此格有障碍,不能通行,1代表可以通过。

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

迷宫不会大于30x30。


输出

判断每个迷宫是否能从左上角的起点走到右下角的终点,每个迷宫输出“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****************************************************************/


本文分享自微信公众号 - WebHub(myWebHub)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
加载中

作者的其它热门文章

打赏
0
0 收藏
分享
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部