fjm小姐姐的烦恼1(判断一个迷宫是否有解)

问题说明
fjm小姐姐现在在一个迷宫里面迷路了,你能帮他判断他是否能走出迷宫吗? (fjm小姐姐只会上下左右移动,不会斜着走,也不会飞)
Input
输入m,n表示迷宫的长和宽1<=n,m<=10。 输入m行n列的字符,其中S表示fjm小姐姐的位置,T表示迷宫出口的位置,*表示可以行走的道路,#表示不可以行走于的墙壁。
Output
如果fjm小姐姐可以走出去那么输出yes 否则输出no

测试用例两组

Sample Input
1 5
S***T
Sample Output
yes
-------------------------------
Sample Input
2 7
S**#**T
***#***
Sample Output
no

参考方法:

/*****************************
* effect:快速判断一个maze是否有解
* author:wyrctzy
* environment:Visual Studio 2019
* time:2018/12/20 03:22
*****************************/
#include "pch.h"
#include<stdio.h>
#include<string.h>
//#include<stdlib.h>
using namespace std;
char** maze;//二维迷宫数组
int** traveled;//迷宫拜访数组
//定义四种可能的移动方式
int move[4][2] = { {1,0},{0,1},{-1,0},{0,-1} };
bool DFS(int n, int m) {
    //遍历上下左右4个点,保证每次只改变x或y坐标 
    for (int i = 0; i < 4; i++) {
        //获得当前的位置 1.行不动,列动→ 2行动,列不动↓ 3.← 4.↑
        int current_n = n + move[i][0], current_m = m + move[i][1];
        if (maze[current_m][current_n] == '*'&&traveled[current_m][current_n] == 0 && maze[current_m][current_n] != '#') {//可通过,而且以前没有走过
            traveled[current_m][current_n] = 1;//标记为已走过这个位置 
            if (DFS(current_n, current_m))
                return  true;
        }
        if (maze[current_m][current_n] == 'T')//终点 
            return true;
    }
    return false;
}
int main() {
    int  m, n;//m行,n列
    int pos_m = 0, pos_n = 0;//起点的xy坐标
    scanf_s("%d%d", &m, &n);
    getchar();//输入数字,后输入字符getchar吃掉回车符
    //C++写法申请一个动态二维数组
    maze = new char*[m+2];
    for (int i = 0; i <=m+2; i++) {
        maze[i] = new char[n+2];
        memset(maze[i], '#', (n + 2) * sizeof(char));
    }
    traveled = new int*[m+2];
    for (int i = 0; i <= m+2; i++) {
        traveled[i] = new int[(n + 2)];
        memset(traveled[i], 0, (n + 2) * sizeof(int));
    }
    //C 写法
    /*maze = (char**)malloc((m + 2) * sizeof(char*));
    for (int i = 0; i < (m + 2); i++) {
        maze[i] = (char*)malloc((n + 2) * sizeof(char));
    }
    traveled = (int**)malloc((m + 2) * sizeof(int*));
    for (int i = 0; i < (m + 2); i++) {
        traveled[i] = (int*)malloc((n + 2) * sizeof(int));
    }*/
    //memset(traveled, 0, sizeof(traveled));错误写法,初始化失败
    //memset(maze, '#', sizeof(maze));
    //注意此处的memset的用法,可以去看我的另一篇文章。
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            scanf_s("%c", &maze[i][j]);
            //找到起点的位置
            if (maze[i][j] == 'S') {
                pos_m = i;
                pos_n = j;
            }
        }//for:j
        getchar();//getchar吃掉回车符
    }//for:i
    /*for (int i = 0; i <= m+1; i++) {
        for (int j = 0; j <= n+1; j++) {
            printf("[%c]\t", maze[i][j]);
        }
        printf("\n");
    }*/
    if (DFS(pos_n, pos_m))
        printf("yes\n");
    else
        printf("no\n");
    return 0;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容