• 牛客网：迷宫问题

    %牛客网：迷宫问题

    在这里插入图片描述

    每博一文案

    白居易说，行路难，不在水，不在山，只在人情，反复间，世间
最不可直视的东西，一是太阳，二是人心。人心，大多难猜，真情总是难遇，
很多时候，我们总是自以为自己在对方心目中很重要。可期望越多，失望就越大。
有人说很多人，突然就不再联系了，和重不重要无关，却和需不需要有人。
每个人都有自己的生活，千万别高估自己在别人心目中的地位。
你以为你是别人心中的唯一，说不定，你就是可有可无的人，人心不是石头。
你对别人怎样，别人心里清楚，感情这座天枰，有来有往，才能维持不变，
愿你即像一个勇士，披荆斩棘，又能有人为你遮风挡雨，不需要刻意讨人喜欢
，只要无愧于心，做好自己。余生，别读感情，别猜人心，学会放过，
是善待自己的最好方式。
                                      ——————   一禅心灵庙语

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    文章目录

    原题：

    在这里插入图片描述

    有关的题目链接: 🔜🔜🔜 牛客网:迷宫问题

    题目分析:

    首先我们从题目中知道了，迷宫中只有一个出口，出口的位置是在(右下角) ，开始位置是 (左上角)，我们需要通

    在这里插入图片描述

    算法，找到出口，并把从 入口 ——> 出口 是路线通过坐标打印出来。

    这里我们使用的是 C语言 代码解决的。0 为通路，1 为障碍物，不可走。

    我们需要遍历整个迷宫，从而找到出口。

    在这里插入图片描述

    我们需要将，我们已经递归遍历走过的，坐标位置，标记成 2 ，防止，往回走过的路，形成（往前走，再往回走，往前走，再往回走）的死循环。如下图:

    在这里插入图片描述

    这里我们使用递归的方式解决：而从题目可知，我们需要将从 入口 ——> 出口 是路线通过坐标打印出来。所以我们需要将坐标保存起来，这里我们使用 栈 将，坐标保存起来。因为 C语言 没有，有关栈的库，所以我们只能自己实现一个栈了。大家可以移动到 🔜🔜🔜( 图文并茂 ，栈的实现 —— C语言_ChinaRainbowSea的博客-CSDN博客 可以将栈的实现的代码，复制粘贴过来，是可以直接使用的。

    解题的代码实现:

    1. 我们将栈创建出来，并且创建好 坐标的结构体 用于保存对应的坐标位置。

    定义一个全局栈: 用于存放我们从 入口 ——> 出口 的路线的坐标。

    #include
#include  // 断言
#include  
#include   // bool 布尔值

// 定义坐标结构体 
typedef struct Postion
{
    int x;     // 数组坐标行
    int y;     // 数组坐标列
}PT;


#define OCE 2             // 扩容的倍数
typedef PT STDatatype;   // 定义该栈中的数据类型,定义为 PT坐标结构类型
/*
* 创建栈的结构体
*/
typedef struct Stack
{
    STDatatype* data;     //动态顺序表开辟空间
    int top;              // 栈顶的标识
    int copacity;         // 栈容量

}ST;


ST path;        // 全局栈

extern void StackInit(ST* st);                     // 初始化栈
extern void StackDestory(ST* st);                  // 销毁栈
extern void StackPush(ST* st, STDatatype x);       // 栈顶入栈操作
extern void StackPop(ST* st);                      // 栈顶出栈操作
extern STDatatype StackTop(ST* st);                // 取栈顶元素
extern int StackSize(ST* st);                      // 求栈中存在的数据个数
extern bool StackEmpty(ST* st);                    // 判断栈是否为空


/*
* 初始化栈
*/
void StackInit(ST* st)
{
    assert(st); // 断言，判断st 不为 NULL；

    st->data = (STDatatype*)malloc(sizeof(STDatatype) * OCE);

    // 判断动态内存(堆上)开辟的空间是否成功
    if (NULL == st->data)
    {
        perror("st->data 动态开辟空间");
        exit(-1);  // 非正常中止程序
    }

    st->copacity = 2;   // 当前栈的容量
    st->top = 0;        // 栈顶位置

    /*
    * top = 0 ,表示的是栈顶的位置是该最后元素的下一个元素的位置
    * top = 1; 表示的是栈顶的位置就是该最后元素的位置
    */
}



/*
* 销毁栈
*/
void StackDestory(ST* st)
{
    assert(st);   // 断言，st是否为空

    free(st->data);  // 释放该内存空间
    st->data = NULL; // 手动置为NULL，防止非法访问
    st->copacity = 0;
    st->top = 0;

}



// 栈顶入栈操作
void StackPush(ST* st, STDatatype x)
{
    assert(st);  // 断言判断,st是否为NULL

    // 判断栈是否满了，满了扩容
    if (st->copacity == st->top)
    {
        // 动态(堆区)扩容开辟空间
        STDatatype* tmp = (STDatatype*)realloc(st->data, st->copacity * OCE * sizeof(STDatatype));

        // 判断动态内存开辟空间是否成功
        if (NULL == tmp)
        {
            perror("tmp 扩容");      // 打印错误报告
            exit(-1);                // 非正常退出
        }
        else
        {
            // 动态开辟空间成功,转移主权
            st->data = tmp;
            st->copacity *= OCE;  // 栈容量扩张
        }
    }

    st->data[st->top] = x;    // 栈顶入栈数值
    st->top++;                // 栈顶加加

}



/*
* 栈顶出栈操作
*/
void StackPop(ST* st)
{
    assert(st);          // 断言判断，st 是否为 NULL

    assert(st->top > 0);   // 出栈的位置必须大于 0 ，不能一直删除没了吧

    st->top--;           // 栈顶位置减减一下，就好了
    /*
    * 注意不可以把 st->data[st->top] = 0; 置为 0 的方式
    * 因为可能你存放的数值就是 0 呢，不就有误导了吗
    */
}



/*
* 取出栈顶元素
*/
STDatatype StackTop(ST* st)
{


    assert(st);  // 断言判断，st 是否为NULL

    assert(st->top > 0);  // 栈不为空

    return st->data[st->top - 1];
    /*
    * -1 ，是因为这里的top 初始化是 0
    * 其top所指向的位置是 该最后一个元素的下一个位置
    */
}



/*
* 求出栈顶元素的个数
*/
int StackSize(ST* st)
{
    assert(st);  // 断言，判断st 是否为 NULL

    return st->top;
    /*
    * 因为是数组，从0 下标开始，但是计数是要 +1 的
    * 而top 刚好就是下一个元素的位置与 计数值相同
    */
}



/*
* 判断该栈是否为空栈
*/
bool StackEmpty(ST* st)
{
    return 0 == st->top;
    /*
    * 判断栈是否为空
    * 当栈顶 top 为 0 是：表示栈没有一个数据，为空栈，返回 false (0)
    * 当栈顶 top 不是 0 时，栈不为空，返回 true (1);
    */
}





void printPath(ST* ps)
{
	ST tmp;    // 定义一个临时拷贝的栈,用于将原栈终点坐标,放入到 tmp 栈的栈底位置,

	StackInit(&tmp);   // 初始化 临时栈

	// 将原来栈的坐标内容 拷贝到 临时栈中(终点作为栈底)
	while (!StackEmpty(ps))
	{
		StackPush(&tmp, StackTop(ps)); // 将原栈的栈顶坐标 ，入栈到tmp临时栈中
		StackPop(ps);  // 出栈,取栈顶元素后,需要出栈,不然无法取到栈后面的数据
	}

	// 
	while (!StackEmpty(&tmp))
	{
		PT top = StackTop(&tmp);    // 取出临时 tmp 栈中的栈顶坐标内容
		printf("(%d,%d)\n", top.x, top.y);  // 打印坐标
		StackPop(&tmp);             // 出栈,取栈顶要与出栈一起,不然无法取到栈后面的数据
	}

	StackDestory(&tmp);    // 销毁临时栈
}



// 判断当前迷宫中的坐标是否存在越界/障碍物, 
bool lsPass(int** mace, int N, int M, PT pos)
{
	if ((pos.x >= 0 && pos.x < N)
		&& (pos.y >= 0 && pos.y < M)   // 没有越界
		&& (mace[pos.x][pos.y] == 0))  // 不是障碍物
	{
		return true;
	}
	else
	{
		return false;
	}

}


    • 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
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226

    1. 首先我们需要创建一个 二维数组 用于存放输入的迷宫结构。

    2. 关于 C语言 二维数组 的实现，因为我们是需要，通过输入数值来确定迷宫的大小的。

    但是在 C语言中，数组的大小必须使用常量值: 1, 2, 3 才行，变量是不可以的 ，如下图：

    在这里插入图片描述

    所以我们只能通过 动态开辟空间创建二维数组 了，才行

    使用 指针数组 ，重点是 数组 ，指针数组: 存放指针的地址的数组。因为是存放的是指针的地址所以，该指针数组是一个 双指针数组 ，

    通过函数 malloc 内存堆区上开辟空间，malloc 在堆区上开辟空间，返回开辟的空间的 首地址，

    在这里插入图片描述

    因为题目中可能输入多组数组迷宫，所以这里我们需要使用上循环的输入scanf("") != EOF ,EOF 数值上是 1，可以理解为是 停止输入的一个标记

    具体代码如下:

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


	while (scanf("%d%d", &N, &M) != EOF) // 输入二维数组的长宽, EOF 不等于 -1 无限输入
	{
		// int arr[N][M] 这样是不行的 在数组里面中的常量必须是，常量值  1,2,3
	    // 所以我们需要使用动态开辟二维数组：
	    // 使用指针数组,重点是指针, 指针数组用于存放指针的地址,

		int** maze = (int**)malloc(sizeof(int*) * N);
		// int** 双指针类型, 指针数组,数组元素是 指针的地址
		//  malloc 返回堆区上开辟的空间的首地址, (int**) 强制转换为双指针,因为我们
		// malloc 开辟类型是 (int*) 指针的地址，自然要使用 双指针才能保存到 指针的地址
		// sizeof(int*)  该指针类型的大小, * 

		// 判断堆区上空间开辟是否成功
		if (NULL == maze)
		{
			perror("maze malloc error");  // 错误提醒
			exit(-1);                 // 程序非正常结束
		}

		for (int i = 0; i < N; i++)
		{
			maze[i] = (int*)malloc(sizeof(int) * M);     // 堆区上开辟空间
			 //判断堆区上空间开辟是否成功
			if (NULL == maze[i])
			{
				perror("maze[i] malloc error");
				exit(-1);
			}
		}


		// 迷宫构造的输入:
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				scanf("%d", &maze[i][j]);
			}
		}

		StackInit(&path);  // 初始化 path全局栈
		PT entry = { 0,0 };   // 定义初始坐标;为 0,0 结构体可以使用花括号全部初始赋值
		if (getMazePath(maze, N, M, entry))   // 递归坐标位置上下左右
		{
			printPath(&path);    // 打印路线坐标
		}
		else
		{
			printf("没有找到通路\n");
		}

		StackDestory(&path);   // 销毁全局栈;
		/*
		* 注意我们这里是通过动态开辟的二维数组(指针数组),
		* 要先将存放到指针数组中的指针的地址的空间先释放掉,再释放指针数组本身的地址空间
		* 如果先释放了指针数组本身的地址空间的话,存放在指针数组中的指针的地址就无法再找到了,成了野指针了
		* 更是无从释放了.
		*/
		for (int i = 0; i < N; i++)  // 释放指针数组中存放的指针的地址
		{
			free(maze[i]);
		}

		free(maze);
		maze = NULL;

	}

	return 0;
}

    • 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

    上述代码解析:

    • while (scanf("%d%d", &N, &M) != EOF) 表示：可以输入多组数据，当不输入数值时(= EOF), 结束循环
    • int** maze = (int**)malloc(sizeof(int*) * N); 创建双指针数组，malloc 堆区上开辟空间

    返回，开辟空间的首地址，这里开辟的是 指针的地址空间 ，所以我们需要 双指针 来保存指针的地址，强制转换为 (int**)

    • PT entry = { 0,0 }; 从入口开始；坐标 (0,0)
    • 最后释放堆区上开辟的空间，我们需要先将保存在二维双指针数组中元素的指针的地址的空间，再释放

    二维双指针数组本身的地址空间，因为如果你释放二维双指针数组本身的地址空间的话，保存在二维数组中

    的指针的地址就再也无法找到了，成了野指针了。

    1. 创建一个函数用于判断当前坐标位置是存在越界，如果越界返回 false ,并且判断该坐标位置是否是障碍物 ，

    是返回 false

    具体代码实现:

    // 判断当前迷宫中的坐标是否存在越界/障碍物, 
bool lsPass(int** mace, int N, int M, PT pos)
{
	if ((pos.x >= 0 && pos.x < N)
		&& (pos.y >= 0 && pos.y < M)   // 没有越界
		&& (mace[pos.x][pos.y] == 0))  // 不是障碍物
	{
		return true;
	}
	else
	{
		return false;
	}

}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    1. 定义一个临时栈，因为我们从 入口——> 出口的中的坐标存入栈中的，栈的特性是先进后出 的特点。而我们

    最后入栈的是出口的坐标 ，导致先从栈取到的是出口的坐标位置，不合题意：入口——> 出口 的坐标，

    所以我们需要通过一个创建一个临时栈，将存放栈顶为出口 的栈的坐标内容，导入到临时栈中，这样临时栈中的

    栈顶坐标是入口 ，栈底是出口 ，再将临时栈中的拷贝到的坐标数据，循环取出就是，入口——> 出口 的坐标了。
    在这里插入图片描述

    具体代码如下:

    void printPath(ST* ps)
{
	ST tmp;    // 定义一个临时拷贝的栈,用于将原栈终点坐标,放入到 tmp 栈的栈底位置,

	StackInit(&tmp);   // 初始化 临时栈

	// 将原来栈的坐标内容 拷贝到 临时栈中(终点作为栈底)
	while (!StackEmpty(ps))
	{
		StackPush(&tmp, StackTop(ps)); // 将原栈的栈顶坐标 ，入栈到tmp临时栈中
		StackPop(ps);  // 出栈,取栈顶元素后,需要出栈,不然无法取到栈后面的数据
	}

	// 
	while (!StackEmpty(&tmp))
	{
		PT top = StackTop(&tmp);    // 取出临时 tmp 栈中的栈顶坐标内容
		printf("(%d,%d)\n", top.x, top.y);  // 打印坐标
		StackPop(&tmp);             // 出栈,取栈顶要与出栈一起,不然无法取到栈后面的数据
	}

	StackDestory(&tmp);    // 销毁临时栈
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    上述代码的注意事项

    注意取了栈顶StackTop(ps)元素后，紧跟着需要StackPop(&tmp)出栈，不然无法取到栈后面的数据内容。

    1. 最后，递归移动坐标的位置，分别是 上下左右，每次都要讲移动的坐标保存到栈中，同时判断该坐标是否，

    到达了，终点右下角,到达终点，返回 true ,每移动一个坐标都需要判断该坐标是否越界，是否是障碍物，最后需要将不是走向终点的坐标，，出栈，防止后面，取栈的数据，不是从入口——> 出口 的坐标了

    具体代码如下:

    // 坐标的上下左右的移动
bool getMazePath(int** maze, int N, int M, PT cur)
{
	StackPush(&path, cur);    // path 全局栈,cur 表示的是当前位置的坐标位置, 存入栈中

	// 判断该坐标位置是否达到终点位置
	if (cur.x == N - 1 && cur.y == M - 1)
	{
		return true;
	}

	PT next;  // 下一个临时坐标,用于保存当前(cur) 的坐标用于后面的移动
	maze[cur.x][cur.y] = 2; // 标记走过的坐标,防止往回走,形成死循环


	// 上走
	next = cur;    //next = cur;  
	next.x = next.x - 1;               // next.x = next.x - 1;
	if (lsPass(maze, N, M, next))    // 判断当前上走后的坐标位置(越界/障碍物),可否继续
	{
		if (getMazePath(maze, N, M, next))   // 可以继续,递归当前上走后的坐标位置,后的上下左右
		{
			return true;
		}
	}


	// 下走
	next = cur;
	next.x = next.x + 1;

	if (lsPass(maze, N, M, next))    // 判断当前下走后的坐标位置(越界/障碍物),可否继续
	{
		if (getMazePath(maze, N, M, next))  // 可以继续,递归当前下后的坐标位置,后的上下左右
		{
			return true;    // 到达终点返回
		}
	}


	// 向左走
	next = cur;
	next.y = next.y - 1;

	if (lsPass(maze, N, M, next))  // 判断当前左走后的坐标位置(越界/障碍物),可否继续
	{
		if (getMazePath(maze, N, M, next)) // 可以继续,递归当前左走后的坐标位置上下左右
		{
			return true;
		}
	}


	// 向右走
	next = cur;
	next.y = next.y + 1;

	if (lsPass(maze, N, M, next))   // 判断当前右走后的坐标位置(越界/障碍物),可否继续
	{
		if (getMazePath(maze, N, M, next))  // 可以继续,递归当前右走后的坐标位置上下左右
		{
			return true;
		}
	}

	StackPop(&path);    // 将保存在栈中不可以走的坐标位置,出栈掉

	return false;
}

    • 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

    上述代码解析:

    • StackPush(&path, cur);表示：path 全局栈,cur 表示的是当前位置的坐标位置, 存入栈中
    • if (cur.x == N - 1 && cur.y == M - 1) 表示：到达终点，右下角
    • if (lsPass(maze, N, M, next)) 表示： 判断当前右走后的坐标位置(越界/障碍物),可否继续
    • if (getMazePath(maze, N, M, next)) 表示：可以继续,递归当前的坐标位置,后的上下左右
    • StackPop(&path); : 将保存在栈中不可以走的坐标位置,出栈掉

    完整代码实现如下:

    #define  _CRT_SECURE_NO_WARNINGS  1

#include
#include  // 断言
#include  
#include   // bool 布尔值

// 定义坐标结构体 
typedef struct Postion
{
    int x;     // 数组坐标行
    int y;     // 数组坐标列
}PT;


#define OCE 2             // 扩容的倍数
typedef PT STDatatype;   // 定义该栈中的数据类型,定义为 PT坐标结构类型
// 输出栈里面的保存的路径
/*
	* 栈是： 后进的先出去，而我们要的是从起点 ———> 终点的一路的坐标
	* 因为我们最后入栈的是终点,栈的原理：后进先出,先从栈取出来的是终点坐标,不合题意
	* 所以我们： 将原来栈的保存的坐标，导入到另外一个栈中,从而将终点坐标放入到栈底了。
	* 这样我们将 拷贝的临时栈中的坐标内容打印出来,就是从起点 ——> 终点的一路的坐标路线。
*/


/*
* 创建栈的结构体
*/
typedef struct Stack
{
    STDatatype* data;     //动态顺序表开辟空间
    int top;              // 栈顶的标识
    int copacity;         // 栈容量

}ST;


ST path;        // 全局栈
/* 函数，变量的声明 extern
* 声明是不会开辟空间的，所以声明可以多次
* 而定义是会开辟空间的，所以定义只能有一次
* 开辟空间不是目的，存放数据才是目的
* 因为只有开辟了空间，才可以存放数据
*
*/

extern void StackInit(ST* st);                     // 初始化栈
extern void StackDestory(ST* st);                  // 销毁栈
extern void StackPush(ST* st, STDatatype x);       // 栈顶入栈操作
extern void StackPop(ST* st);                      // 栈顶出栈操作
extern STDatatype StackTop(ST* st);                // 取栈顶元素
extern int StackSize(ST* st);                      // 求栈中存在的数据个数
extern bool StackEmpty(ST* st);                    // 判断栈是否为空
//extern void TestStack(ST* st);                     // 对于栈的测试



/*
* 初始化栈
*/
void StackInit(ST* st)
{
    assert(st); // 断言，判断st 不为 NULL；

    st->data = (STDatatype*)malloc(sizeof(STDatatype) * OCE);

    // 判断动态内存(堆上)开辟的空间是否成功
    if (NULL == st->data)
    {
        perror("st->data 动态开辟空间");
        exit(-1);  // 非正常中止程序
    }

    st->copacity = 2;   // 当前栈的容量
    st->top = 0;        // 栈顶位置

    /*
    * top = 0 ,表示的是栈顶的位置是该最后元素的下一个元素的位置
    * top = 1; 表示的是栈顶的位置就是该最后元素的位置
    */
}



/*
* 销毁栈
*/
void StackDestory(ST* st)
{
    assert(st);   // 断言，st是否为空

    free(st->data);  // 释放该内存空间
    st->data = NULL; // 手动置为NULL，防止非法访问
    st->copacity = 0;
    st->top = 0;

}



// 栈顶入栈操作
void StackPush(ST* st, STDatatype x)
{
    assert(st);  // 断言判断,st是否为NULL

    // 判断栈是否满了，满了扩容
    if (st->copacity == st->top)
    {
        // 动态(堆区)扩容开辟空间
        STDatatype* tmp = (STDatatype*)realloc(st->data, st->copacity * OCE * sizeof(STDatatype));

        // 判断动态内存开辟空间是否成功
        if (NULL == tmp)
        {
            perror("tmp 扩容");      // 打印错误报告
            exit(-1);                // 非正常退出
        }
        else
        {
            // 动态开辟空间成功,转移主权
            st->data = tmp;
            st->copacity *= OCE;  // 栈容量扩张
        }
    }

    st->data[st->top] = x;    // 栈顶入栈数值
    st->top++;                // 栈顶加加

}



/*
* 栈顶出栈操作
*/
void StackPop(ST* st)
{
    assert(st);          // 断言判断，st 是否为 NULL

    assert(st->top > 0);   // 出栈的位置必须大于 0 ，不能一直删除没了吧

    st->top--;           // 栈顶位置减减一下，就好了
    /*
    * 注意不可以把 st->data[st->top] = 0; 置为 0 的方式
    * 因为可能你存放的数值就是 0 呢，不就有误导了吗
    */
}



/*
* 取出栈顶元素
*/
STDatatype StackTop(ST* st)
{


    assert(st);  // 断言判断，st 是否为NULL

    assert(st->top > 0);  // 栈不为空

    return st->data[st->top - 1];
    /*
    * -1 ，是因为这里的top 初始化是 0
    * 其top所指向的位置是 该最后一个元素的下一个位置
    */
}



/*
* 求出栈顶元素的个数
*/
int StackSize(ST* st)
{
    assert(st);  // 断言，判断st 是否为 NULL

    return st->top;
    /*
    * 因为是数组，从0 下标开始，但是计数是要 +1 的
    * 而top 刚好就是下一个元素的位置与 计数值相同
    */
}



/*
* 判断该栈是否为空栈
*/
bool StackEmpty(ST* st)
{
    return 0 == st->top;
    /*
    * 判断栈是否为空
    * 当栈顶 top 为 0 是：表示栈没有一个数据，为空栈，返回 false (0)
    * 当栈顶 top 不是 0 时，栈不为空，返回 true (1);
    */
}





void printPath(ST* ps)
{
	ST tmp;    // 定义一个临时拷贝的栈,用于将原栈终点坐标,放入到 tmp 栈的栈底位置,

	StackInit(&tmp);   // 初始化 临时栈

	// 将原来栈的坐标内容 拷贝到 临时栈中(终点作为栈底)
	while (!StackEmpty(ps))
	{
		StackPush(&tmp, StackTop(ps)); // 将原栈的栈顶坐标 ，入栈到tmp临时栈中
		StackPop(ps);  // 出栈,取栈顶元素后,需要出栈,不然无法取到栈后面的数据
	}

	// 
	while (!StackEmpty(&tmp))
	{
		PT top = StackTop(&tmp);    // 取出临时 tmp 栈中的栈顶坐标内容
		printf("(%d,%d)\n", top.x, top.y);  // 打印坐标
		StackPop(&tmp);             // 出栈,取栈顶要与出栈一起,不然无法取到栈后面的数据
	}

	StackDestory(&tmp);    // 销毁临时栈
}



// 判断当前迷宫中的坐标是否存在越界/障碍物, 
bool lsPass(int** mace, int N, int M, PT pos)
{
	if ((pos.x >= 0 && pos.x < N)
		&& (pos.y >= 0 && pos.y < M)   // 没有越界
		&& (mace[pos.x][pos.y] == 0))  // 不是障碍物
	{
		return true;
	}
	else
	{
		return false;
	}

}



// 坐标的上下左右的移动
bool getMazePath(int** maze, int N, int M, PT cur)
{
	StackPush(&path, cur);    // path 全局栈,cur 表示的是当前位置的坐标位置, 存入栈中

	// 判断该坐标位置是否达到终点位置
	if (cur.x == N - 1 && cur.y == M - 1)
	{
		return true;
	}

	PT next;  // 下一个临时坐标,用于保存当前(cur) 的坐标用于后面的移动
	maze[cur.x][cur.y] = 2; // 标记走过的坐标,防止往回走,形成死循环


	// 上走
	next = cur;    //next = cur;  
	next.x = next.x - 1;               // next.x = next.x - 1;
	if (lsPass(maze, N, M, next))    // 判断当前上走后的坐标位置(越界/障碍物),可否继续
	{
		if (getMazePath(maze, N, M, next))   // 可以继续,递归当前上走后的坐标位置,后的上下左右
		{
			return true;
		}
	}


	// 下走
	next = cur;
	next.x = next.x + 1;

	if (lsPass(maze, N, M, next))    // 判断当前下走后的坐标位置(越界/障碍物),可否继续
	{
		if (getMazePath(maze, N, M, next))  // 可以继续,递归当前下后的坐标位置,后的上下左右
		{
			return true;    // 到达终点返回
		}
	}


	// 向左走
	next = cur;
	next.y = next.y - 1;

	if (lsPass(maze, N, M, next))  // 判断当前左走后的坐标位置(越界/障碍物),可否继续
	{
		if (getMazePath(maze, N, M, next)) // 可以继续,递归当前左走后的坐标位置上下左右
		{
			return true;
		}
	}


	// 向右走
	next = cur;
	next.y = next.y + 1;

	if (lsPass(maze, N, M, next))   // 判断当前右走后的坐标位置(越界/障碍物),可否继续
	{
		if (getMazePath(maze, N, M, next))  // 可以继续,递归当前右走后的坐标位置上下左右
		{
			return true;
		}
	}

	StackPop(&path);    // 将保存在栈中不可以走的坐标位置,出栈掉

	return false;
}



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


	while (scanf("%d%d", &N, &M) != EOF) // 输入二维数组的长宽, EOF 不等于 -1 无限输入
	{
		// int arr[N][M] 这样是不行的 在数组里面中的常量必须是，常量值  1,2,3
	// 所以我们需要使用动态开辟二维数组：
	// 使用指针数组,重点是指针, 指针数组用于存放指针的地址,

		int** maze = (int**)malloc(sizeof(int*) * N);
		// int** 双指针类型, 指针数组,数组元素是 指针的地址
		//  malloc 返回堆区上开辟的空间的首地址, (int**) 强制转换为双指针,因为我们
		// malloc 开辟类型是 (int*) 指针的地址，自然要使用 双指针才能保存到 指针的地址
		// sizeof(int*)  该指针类型的大小, * 

		// 判断堆区上空间开辟是否成功
		if (NULL == maze)
		{
			perror("maze malloc error");  // 错误提醒
			exit(-1);                 // 程序非正常结束
		}

		for (int i = 0; i < N; i++)
		{
			maze[i] = (int*)malloc(sizeof(int) * M);     // 堆区上开辟空间

			 //判断堆区上空间开辟是否成功
			if (NULL == maze[i])
			{
				perror("maze[i] malloc error");
				exit(-1);
			}
		}


		// 迷宫构造的输入:
		for (int i = 0; i < N; i++)
		{
			for (int j = 0; j < M; j++)
			{
				scanf("%d", &maze[i][j]);
			}
		}

		StackInit(&path);  // 初始化 path全局栈
		PT entry = { 0,0 };   // 定义初始坐标;为 0,0 结构体可以使用花括号全部初始赋值

		if (getMazePath(maze, N, M, entry))
		{
			printPath(&path);    // 打印路线坐标
		}
		else
		{
			printf("没有找到通路\n");
		}

		StackDestory(&path);   // 销毁全局栈;
		/*
		* 注意我们这里是通过动态开辟的二维数组(指针数组),
		* 要先将存放到指针数组中的指针的地址的空间先释放掉,再释放指针数组本身的地址空间
		* 如果先释放了指针数组本身的地址空间的话,存放在指针数组中的指针的地址就无法再找到了,成了野指针了
		* 更是无从释放了.
		*/
		for (int i = 0; i < N; i++)  // 释放指针数组中存放的指针的地址
		{
			free(maze[i]);
		}

		free(maze);
		maze = NULL;

	}

	return 0;
}


    • 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
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289
    • 290
    • 291
    • 292
    • 293
    • 294
    • 295
    • 296
    • 297
    • 298
    • 299
    • 300
    • 301
    • 302
    • 303
    • 304
    • 305
    • 306
    • 307
    • 308
    • 309
    • 310
    • 311
    • 312
    • 313
    • 314
    • 315
    • 316
    • 317
    • 318
    • 319
    • 320
    • 321
    • 322
    • 323
    • 324
    • 325
    • 326
    • 327
    • 328
    • 329
    • 330
    • 331
    • 332
    • 333
    • 334
    • 335
    • 336
    • 337
    • 338
    • 339
    • 340
    • 341
    • 342
    • 343
    • 344
    • 345
    • 346
    • 347
    • 348
    • 349
    • 350
    • 351
    • 352
    • 353
    • 354
    • 355
    • 356
    • 357
    • 358
    • 359
    • 360
    • 361
    • 362
    • 363
    • 364
    • 365
    • 366
    • 367
    • 368
    • 369
    • 370
    • 371
    • 372
    • 373
    • 374
    • 375
    • 376
    • 377
    • 378
    • 379
    • 380
    • 381
    • 382
    • 383
    • 384
    • 385
    • 386
    • 387
    • 388
    • 389
    • 390
    • 391
    • 392
    • 393
    • 394
    • 395
    • 396
    • 397
    • 398
    • 399

    在这里插入图片描述

    在这里插入图片描述

    迷宫最短路径求解

    下面是难度上升的，迷宫问题：

    原题目链接: 🔜🔜🔜 地下迷宫_滴滴笔试题_牛客网 (nowcoder.com)

    在这里插入图片描述

    解题代码实现如下：

    #include
#include
#include
#include   // bool 布尔值

typedef struct Postion
{
    int row;
    int col;
}PT;
/
typedef PT STDataType;

typedef struct Stack
{
	STDataType* a;
	int top;
	int capacity;
}ST, Stack;



void StackInit(ST* ps);
void StackDestory(ST* ps);
// 入栈
void StackPush(ST* ps, STDataType x);
// 出栈
void StackPop(ST* ps);
STDataType StackTop(ST* ps);

int StackSize(ST* ps);
bool StackEmpty(ST* ps);

void StackInit(ST* ps)
{
	assert(ps);

	ps->a = (STDataType*)malloc(sizeof(STDataType) * 4);
	if (ps->a == NULL)
	{
		printf("malloc fail\n");
		exit(-1);
	}

	ps->capacity = 4;
	ps->top = 0;
}

void StackDestory(ST* ps)
{
	assert(ps);
	free(ps->a);
	ps->a = NULL;
	ps->top = ps->capacity = 0;
}

// 入栈
void StackPush(ST* ps, STDataType x)
{
	assert(ps);

	// 满了-》增容
	if (ps->top == ps->capacity)
	{
		STDataType* tmp = (STDataType*)realloc(ps->a, ps->capacity * 2 * sizeof(STDataType));
		if (tmp == NULL)
		{
			printf("realloc fail\n");
			exit(-1);
		}
		else
		{
			ps->a = tmp;
			ps->capacity *= 2;
		}
	}

	ps->a[ps->top] = x;
	ps->top++;
}

// 出栈
void StackPop(ST* ps)
{
	assert(ps);
	// 栈空了，调用Pop，直接中止程序报错
	assert(ps->top > 0);

	//ps->a[ps->top - 1] = 0;
	ps->top--;
}

STDataType StackTop(ST* ps)
{
	assert(ps);
	// 栈空了，调用Top，直接中止程序报错
	assert(ps->top > 0);

	return ps->a[ps->top - 1];
}

int StackSize(ST* ps)
{
	assert(ps);

	return ps->top;
}

bool StackEmpty(ST* ps)
{
	assert(ps);

	return ps->top == 0;
}

Stack path;
Stack minpath;

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

// 输出栈里面的坐标路径
void PirntPath(Stack* ps)
{
	// path数据倒到rPath
	Stack rPath;
	StackInit(&rPath);
	while (!StackEmpty(ps))
	{
		StackPush(&rPath, StackTop(ps));
		StackPop(ps);
	}

	while (StackSize(&rPath) > 1)
	{
		PT top = StackTop(&rPath);
		printf("[%d,%d],", top.row, top.col);
		StackPop(&rPath);
	}

	PT top = StackTop(&rPath);
	printf("[%d,%d]", top.row, top.col);
	StackPop(&rPath);

	StackDestory(&rPath);
}

bool IsPass(int** maze, int N, int M, PT pos)
{
	if (pos.row >= 0 && pos.row < N
		&& pos.col >= 0 && pos.col < M
		&& maze[pos.row][pos.col] == 1)
	{
		return true;
	}
	else
	{
		return false;
	}
}

void StackCopy(Stack* ppath, Stack* pcopy)
{
	pcopy->a = (STDataType*)malloc(sizeof(STDataType*)*ppath->capacity);
	memcpy(pcopy->a, ppath->a, sizeof(STDataType)*ppath->top);
	pcopy->top = ppath->top;
	pcopy->capacity = ppath->capacity;
}

void GetMazePath(int** maze, int N, int M, PT cur, int P)
{
	StackPush(&path, cur);

	// 如果走到出口
	if (cur.row == 0 && cur.col == M - 1)
	{
		// 找到了更短的路径，更新minpath；
		if (P >= 0 && StackEmpty(&minpath)
			|| StackSize(&path) < StackSize(&minpath))
		{
			StackDestory(&minpath);
			StackCopy(&path, &minpath);
		}
	}

	// 探测cur位置得上下左右四个方向
	PT next;
	maze[cur.row][cur.col] = 2;

	// 上
	next = cur;
	next.row -= 1;
	if (IsPass(maze, N, M, next))
	{
		GetMazePath(maze, N, M, next, P - 3);

	}

	// 下
	next = cur;
	next.row += 1;
	if (IsPass(maze, N, M, next))
	{
		GetMazePath(maze, N, M, next, P);
	}


	// 左
	next = cur;
	next.col -= 1;
	if (IsPass(maze, N, M, next))
	{
		GetMazePath(maze, N, M, next, P - 1);
	}

	// 右
	next = cur;
	next.col += 1;
	if (IsPass(maze, N, M, next))
	{
		GetMazePath(maze, N, M, next, P - 1);
	}

	// 恢复一下
	maze[cur.row][cur.col] = 1;
	StackPop(&path);
}

int main()
{
	int N = 0, M = 0, P = 0;
	while (scanf("%d%d%d", &N, &M, &P) != EOF)
	{
		// int a[n][m]; // vs2013 不支持
		// 动态开辟二维数组
		int** maze = (int**)malloc(sizeof(int*)*N);
		for (int i = 0; i < N; ++i)
		{
			maze[i] = (int*)malloc(sizeof(int)*M);
		}

		// 二维数组得输入
		for (int i = 0; i < N; ++i)
		{
			for (int j = 0; j < M; ++j)
			{
				scanf("%d", &maze[i][j]);
			}
		}

		StackInit(&path);
		StackInit(&minpath);
		// PrintMaze(maze, N, M);
		PT entry = { 0, 0 };
		GetMazePath(maze, N, M, entry, P);
        
        if(!StackEmpty(&minpath))
        {
            PirntPath(&minpath);
        }
        else
        {
            printf("Can not escape!\n");
        }
		

		StackDestory(&path);
		StackDestory(&minpath);

		for (int i = 0; i < N; ++i)
		{
			free(maze[i]);
		}
		free(maze);
		maze = NULL;
	}

	return 0;
}

    • 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
    • 187
    • 188
    • 189
    • 190
    • 191
    • 192
    • 193
    • 194
    • 195
    • 196
    • 197
    • 198
    • 199
    • 200
    • 201
    • 202
    • 203
    • 204
    • 205
    • 206
    • 207
    • 208
    • 209
    • 210
    • 211
    • 212
    • 213
    • 214
    • 215
    • 216
    • 217
    • 218
    • 219
    • 220
    • 221
    • 222
    • 223
    • 224
    • 225
    • 226
    • 227
    • 228
    • 229
    • 230
    • 231
    • 232
    • 233
    • 234
    • 235
    • 236
    • 237
    • 238
    • 239
    • 240
    • 241
    • 242
    • 243
    • 244
    • 245
    • 246
    • 247
    • 248
    • 249
    • 250
    • 251
    • 252
    • 253
    • 254
    • 255
    • 256
    • 257
    • 258
    • 259
    • 260
    • 261
    • 262
    • 263
    • 264
    • 265
    • 266
    • 267
    • 268
    • 269
    • 270
    • 271
    • 272
    • 273
    • 274
    • 275
    • 276
    • 277
    • 278
    • 279
    • 280
    • 281
    • 282
    • 283
    • 284
    • 285
    • 286
    • 287
    • 288
    • 289

    在这里插入图片描述

    最后:

    限于自身水平，其中存在的错误，希望大家给予指教，韩信点兵——多多益善，谢谢大家，后会有期，江湖再见 ！！！

    在这里插入图片描述

  • 相关阅读:
    一种新型侧信道攻击方法，影响大部分苹果 A&M 系列芯片
    Proximal Policy Optimization近端策略优化（PPO）
    二叉排序树（BST）
    模型分类model
    2022.11.2 英语背诵
    计算机毕设（附源码）JAVA-SSM基于的小型房屋租赁平台
    @Transactional 注解使用详解
    百度之星（数学基础题）
    力扣刷题-字符串-反转字符串Ⅱ
    pycharm打包Python程序运行闪退的问题
  • 原文地址：https://blog.csdn.net/weixin_61635597/article/details/126751238