(文章目录)

前言

原题：
https://www.nowcoder.com/practice/cf24906056f4488c9ddb132f317e03bc?tpId=37&tqId=21266&ru=/exam/oj

一、题目要求

1.输入

输入两个整数，N与M，分别代表二维数组的行数与列数。再输入对应的值，1代表墙壁，0代表可走的路，迷宫只有唯一一条通道可走。
（0，0）为入口
（N - 1， M - 1）为出口
数据范围：2 <= N <= 10，2 <= M<= 10
数组中仅包含0和1
示例：

2.输出

纵向输出从入口到出口的路径
示例：

二、思路与算法

本题采用深度优先搜索+栈的思路，从入口开始走，每次走过的路标记为2（入栈），若走到某一条不通的路线，则返回到该路线的起点处（把不通的路线出栈），再走没走过的路，直到找到出口为止。
C语言实现栈教程移步下方链接⬇️⬇️⬇️🥺
http://t.csdnimg.cn/8cAkt

三、代码实现

1.创建迷宫

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
typedef struct path {
    int row;
    int col;
} path;

int main(){
    int i = 0;
    int N = 0, M = 0;//用来接收迷宫的行数（N）与列数（M）

    while (scanf("%d%d", &N, &M) != EOF){//可能会创建多个迷宫，因此用EOF来判断循环是否终止
        int** maze = (int**)malloc(sizeof(int*)*N);//动态开辟行数，N行
        for (i = 0; i < N; i++){
            maze[i] = (int*)malloc(sizeof(int)*M);//给每一行都为M个数，M列
        }
        for (i = 0; i < N; i++){
            int j = 0;
            for (j = 0; j < M; j++){
                scanf("%d", &maze[i][j]);//布置迷宫
            }
        }
        path cur = {0,0};//创建一个用来存放迷宫坐标的结构体，赋初始值为迷宫的入口
        stack exitPath;//创建用来存放迷宫出口路径的栈
        StackInit(&exitPath);//初始化栈
        FindMazeExit(maze, N, M, cur, &exitPath);//寻找迷宫的出口路径
        PrintMazeExitPath(exitPath);//打印迷宫的出口路径
    }
}

2.寻找迷宫的出口路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
//判断当前路径的坐标是否可走
bool isPass(int** maze, int row, int col, path cur){
    if (cur.row < row && cur.col < col
    && cur.row >= 0 && cur.col >= 0 && maze[cur.row][cur.col] == 0){
        return true;
    }
    return false;
}

//寻找出路
bool FindMazeExit(int** maze, int N, int M, path cur, stack* exitPath){
    StackPush(exitPath, cur);//将当前到达的路径坐标入栈
    maze[cur.row][cur.col] = 2;//走过的路赋值为2

    if (cur.row == N - 1 && cur.col == M - 1){//若当前坐标为出口返回真
        return true;
    }
    path next = cur;//存放当前坐标，寻找下一个可通的坐标

    //向迷宫的上方寻找
    next.row--;
    if (isPass(maze, N, M, next)){//若该坐标可走
        if (FindMazeExit(maze, N, M, next, exitPath)){//则递归该坐标
            return true;
        }
    }

    //向迷宫的下方寻找
    next = cur;
    next.row++;
    if (isPass(maze, N, M, next)){
        if (FindMazeExit(maze, N, M, next, exitPath)){
            return true;
        }
    }

    //向迷宫的左方寻找
    next = cur;
    next.col++;
    if (isPass(maze, N, M, next)){
        if (FindMazeExit(maze, N, M, next, exitPath)){
            return true;
        }
    }

    //向迷宫的右方寻找
    next = cur;
    next.col--;
    if (isPass(maze, N, M, next)){
        if (FindMazeExit(maze, N, M, next, exitPath)){
            return true;
        }
    }

    StackPop(exitPath);//如果当前路径的坐标为死路，就将当前坐标出栈
    return false;//并且返回false
}

3.输出迷宫的出口路径

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void PrintMazeExitPath(stack p){
    //因为保存的路径是颠倒的，所以要反转一下再输出
    stack reversePath;//创建一个用来保存反转后路径的栈
    StackInit(&reversePath);//初始化
    while (!StackEmpty(&p)){//若栈为空，循环停止
        StackPush(&reversePath, StackTop(&p));//取出栈顶数据，并入到reversePath
        StackPop(&p);//将栈顶出栈
    }
    //打印反转后的路径
    while (!StackEmpty(&reversePath)){//若栈为空，循环停止
        path cur = StackTop(&reversePath);//将栈顶数据取出
        printf("(%d,%d)\n", cur.row, cur.col);//打印坐标
        StackPop(&reversePath);//出栈
    }
}

四、完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>

typedef struct path {
    int row;
    int col;
} path;

typedef path StackDataType;

typedef struct Stack {
	StackDataType* vals;
	int top;
	int capacity;
}stack;

void StackInit(stack* p) {
	assert(p);

	p->vals = (StackDataType*)malloc(sizeof(StackDataType) * 4);
	p->capacity = 4;
	p->top = 0;
}

void StackDestroy(stack* p) {
	assert(p);
	free(p->vals);
	p->vals = NULL;
	p->capacity = p->top = 0;
}

void StackPush(stack* p, StackDataType x) {
	assert(p);

	if (p->top == p->capacity) {
		StackDataType* tmp = (StackDataType*)realloc(p->vals, sizeof(StackDataType) * (p->capacity * 2));
		if (tmp) {
			p->capacity *= 2;
			p->vals = tmp;
		}
		else {
			printf("realloc fail!\n");
			exit(-1);
		}
	}
	p->vals[p->top] = x;
	p->top++;
}

void StackPop(stack* p) {
	assert(p);

	if (p->top > 0) {
		p->top--;
	}
	else {
		printf("stack no data\n");
		exit(-1);
	}
}

StackDataType StackTop(stack* p) {
	assert(p);

	if (p->top == 0) {
		printf("stack no data\n");
		exit(-1);
	}
	else {
		return p->vals[p->top - 1];
	}
}

int StackSize(stack* p) {
	assert(p);

	return p->top;
}

bool StackEmpty(stack* p) {
	assert(p);

	return p->top == 0;
}

void PrintMaze(int** maze, int row, int col){
    int i = 0;
    for (i = 0; i < row; i++){
        int j = 0;
        for (j = 0; j < col; j++){
            printf("%d ", maze[i][j]);
        }
        printf("\n");
    }
}

bool isPass(int** maze, int row, int col, path cur){
    if (cur.row < row && cur.col < col
    && cur.row >= 0 && cur.col >= 0 && maze[cur.row][cur.col] == 0){
        return true;
    }
    return false;
}

bool FindMazeExit(int** maze, int N, int M, path cur, stack* exitPath){
    StackPush(exitPath, cur);
    maze[cur.row][cur.col] = 2;

    if (cur.row == N - 1 && cur.col == M - 1){
        return true;
    }
    path next = cur;

    next.row--;
    if (isPass(maze, N, M, next)){
        if (FindMazeExit(maze, N, M, next, exitPath)){
            return true;
        }
    }

    next = cur;
    next.row++;
    if (isPass(maze, N, M, next)){
        if (FindMazeExit(maze, N, M, next, exitPath)){
            return true;
        }
    }

    next = cur;
    next.col++;
    if (isPass(maze, N, M, next)){
        if (FindMazeExit(maze, N, M, next, exitPath)){
            return true;
        }
    }

    next = cur;
    next.col--;
    if (isPass(maze, N, M, next)){
        if (FindMazeExit(maze, N, M, next, exitPath)){
            return true;
        }
    }

    StackPop(exitPath);
    return false;
}

void PrintMazeExitPath(stack p){
    stack reversePath;
    StackInit(&reversePath);
    while (!StackEmpty(&p)){
        StackPush(&reversePath, StackTop(&p));
        StackPop(&p);
    }
    while (!StackEmpty(&reversePath)){
        path cur = StackTop(&reversePath);
        printf("(%d,%d)\n", cur.row, cur.col);
        StackPop(&reversePath);
    }
}

int main(){
    int i = 0;
    int N = 0, M = 0;

    while (scanf("%d%d", &N, &M) != EOF){
        int** maze = (int**)malloc(sizeof(int*)*N);
        for (i = 0; i < N; i++){
            maze[i] = (int*)malloc(sizeof(int)*M);
        }
        for (i = 0; i < N; i++){
            int j = 0;
            for (j = 0; j < M; j++){
                scanf("%d", &maze[i][j]);
            }
        }
        path cur = {0,0};
        stack exitPath;
        StackInit(&exitPath);
        FindMazeExit(maze, N, M, cur, &exitPath);
        PrintMazeExitPath(exitPath);
    }
}

一开始写在csdn的，现在搬上来凑个数

csdn文章链接

说些什么吧！

waline