前言:本章記錄作者學(xué)習(xí)中，遇到的兩個(gè)比較有趣的問(wèn)題，一個(gè)簡(jiǎn)單和一個(gè)較復(fù)雜的迷宮問(wèn)題。
?
?
一、迷宮問(wèn)題的思路
讓我們先來(lái)看簡(jiǎn)單的：迷宮問(wèn)題
它的具體要求：
輸入描述：
輸入兩個(gè)整數(shù)，分別表示二維數(shù)組的行數(shù)，列數(shù)。再輸入相應(yīng)的數(shù)組，其中的1表示墻壁，0表示可以走的路。數(shù)據(jù)保證有唯一解,不考慮有多解的情況，即迷宮只有一條通道。
如
5 5
0 1 0 0 0
0 1 1 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
要求輸出 如：
(0,0)
(1,0)
(2,0)
(2,1)
(2,2)
(2,3)
(2,4)
(3,4)
(4,4)
這道題的重點(diǎn)有：只能上下左右走，不能斜著走；左上角為起點(diǎn)，右下角為終點(diǎn)；只有唯一解。
思路分析：
- 對(duì)于不支持變長(zhǎng)數(shù)組的C版本來(lái)說(shuō)，如果需要實(shí)現(xiàn)二維變長(zhǎng)數(shù)組的話，就需要動(dòng)態(tài)開辟二維數(shù)組。
- 每次需要對(duì)上下左右四個(gè)方向進(jìn)行判斷，才能到達(dá)下一個(gè)坐標(biāo)，并且如果四個(gè)方向都不能走而且還沒到達(dá)終點(diǎn)，那么就要往回走。
- 為了判斷往回是否還有其它能走的方向，我們需要對(duì)走過(guò)的坐標(biāo)進(jìn)行標(biāo)記，這樣就不會(huì)出現(xiàn)走重復(fù)的路線。
- 在結(jié)束的時(shí)候，我們需要打印這條路徑的每個(gè)坐標(biāo)，那么我們就需要對(duì)我們走過(guò)的坐標(biāo)進(jìn)行儲(chǔ)存，對(duì)到達(dá)不了終點(diǎn)的路上的坐標(biāo)消除，所以似乎需要棧來(lái)幫我們儲(chǔ)存這個(gè)坐標(biāo)。
?
?
二、簡(jiǎn)單迷宮的代碼實(shí)現(xiàn)
動(dòng)態(tài)實(shí)現(xiàn)二維變長(zhǎng)數(shù)組：
先創(chuàng)建一個(gè)二維指針，儲(chǔ)存N個(gè)一維指針的地址，這些一維指針都分別指向一個(gè)開辟了M個(gè)數(shù)據(jù)的數(shù)組
#include<stdio.h>
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");
}
}
int main()
{
int N = 0, M = 0;
scanf("%d %d", &N, &M);
//動(dòng)態(tài)開辟二維數(shù)組
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]);
}
}
PrintMaze(maze, N, M);//測(cè)試是否能打印，看看有沒有問(wèn)題
for (int i = 0; i < N; i++)
{
free(maze[i]);
}
free(maze);
return 0;
}
?
?
四個(gè)方向判斷的實(shí)現(xiàn)：
為了方便操作，我們建立一個(gè)結(jié)構(gòu)體類型，方便定義坐標(biāo)。
typedef struct position
{
int row;
int col;
}PT;
并且在測(cè)試頁(yè)定義初始變量：
PT cur = { 0,0 };
- 從（0，0）坐標(biāo)開始，假設(shè)先判斷上下，再判斷左右，如果能通過(guò)就移動(dòng)坐標(biāo)，并且進(jìn)入下次判斷，直到到達(dá)終點(diǎn)，或者不能移動(dòng)，并且需要對(duì)每次到達(dá)的坐標(biāo)進(jìn)行標(biāo)記，假設(shè)標(biāo)記為2.
- 如果四個(gè)方向都不能走，并且沒到達(dá)終點(diǎn)，那么將一直返回上一個(gè)位置，直到有其它方向能走。
- 如果到達(dá)終點(diǎn)，返回true，直到跳出所有遞歸。
//判斷下一個(gè)坐標(biāo)是否能通過(guò)
bool IsPass(int** maze, int N, int M, PT cur)
{
if (cur.col >= 0 && cur.col < M && cur.row >= 0 && cur.row < N
&& maze[cur.row][cur.col] == 0)
{
return true;
}
else
{
return false;
}
}
bool GetPath(int** maze, int N, int M, PT cur)
{
//到達(dá)終點(diǎn)
if (cur.row == N - 1 && cur.col == M - 1)
{
return true;
}
//上下左右判斷
PT next;
maze[cur.row][cur.col] = 2;//標(biāo)記
//上
next = cur;
next.row -= 1;
if (IsPass(maze, N, M, next))
{
//上方向可以通過(guò)就移動(dòng)到上方向的坐標(biāo)，并且繼續(xù)判斷四個(gè)方向是否可以移動(dòng)
if (GetPath(maze, N, M, next))
{
//1.只有到達(dá)終點(diǎn)才會(huì)進(jìn)入這次判斷，并且一直返回true，直到退出所有遞歸。
//2.因?yàn)檫@題只有唯一解，所以一旦找到終點(diǎn)就可以直接返回。
return true;
}
}
//下
next = cur;
next.row += 1;
if (IsPass(maze, N, M, next))
{
if (GetPath(maze, N, M, next))
{
return true;
}
}
//左
next = cur;
next.col -= 1;
if (IsPass(maze, N, M, next))
{
if (GetPath(maze, N, M, next))
{
return true;
}
}
//右
next = cur;
next.col += 1;
if (IsPass(maze, N, M, next))
{
if (GetPath(maze, N, M, next))
{
return true;
}
}
//四個(gè)方向都不能走，就返回false，跳到上一個(gè)坐標(biāo)判斷它剩下的其它方向是否可以走
return false;
}
?
?
利用棧記錄坐標(biāo)的實(shí)現(xiàn)：
因?yàn)镃語(yǔ)言沒有自己的棧，所以我們還需要自己搭建一個(gè)棧。
棧的實(shí)現(xiàn)
- 每次判斷坐標(biāo)前，先將當(dāng)前坐標(biāo)存入棧中，如果四個(gè)方向都不能走的時(shí)候，再出棧。
- 當(dāng)?shù)竭_(dá)終點(diǎn)，返回完后，對(duì)棧中數(shù)據(jù)進(jìn)行處理。
- 因?yàn)闂Ｖ袛?shù)據(jù)打印后與題目要求的打印相反，所有需要再創(chuàng)建一個(gè)棧，將當(dāng)前棧中的數(shù)據(jù)導(dǎo)入另一個(gè)棧中，從而實(shí)現(xiàn)相反的打印。
完整代碼：
#include<stdio.h>;
#include<stdlib.h>;
#include<assert.h>;
#include<stdbool.h>;
typedef struct position
{
int row;
int col;
}PT;
typedef PT STDataType;
typedef struct stack {
STDataType* a;
int top;
int capacity;
}ST;
void StackInit(ST*ps);
void StackDestroy(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) {
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;//或者-1
}
void StackPush(ST* ps, STDataType x) {
if (ps->capacity == ps->top) {
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL) {
printf("realloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top++] = x;
}
void StackDestroy(ST* ps) {
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
void StackPop(ST* ps) {
assert(ps);
/*assert(ps->top > 0);*/
assert(!StackEmpty(ps));
ps->top--;
}
STDataType StackTop(ST* ps) {
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top-1];
}
int StackSize(ST* ps) {
assert(ps);
return ps->top;
}
bool StackEmpty(ST* ps) {
return ps->top==0;
}
//
ST path;//可以創(chuàng)局部變量，這里方便一下
bool IsPass(int** maze, int N, int M, PT cur)
{
if (cur.col >= 0 && cur.col < M && cur.row >= 0 && cur.row < N
&& maze[cur.row][cur.col] == 0)
{
return true;
}
else
{
return false;
}
}
bool GetPath(int** maze, int N, int M, PT cur)
{
//走過(guò)的坐標(biāo)先入棧
StackPush(&path, cur);
//到達(dá)終點(diǎn)
if (cur.row == N - 1 && cur.col == M - 1)
{
return true;
}
//上下左右判斷
PT next;
maze[cur.row][cur.col] = 2;
//上
next = cur;
next.row -= 1;
if (IsPass(maze, N, M, next))
{
if (GetPath(maze, N, M, next))
{
return true;
}
}
//下
next = cur;
next.row += 1;
if (IsPass(maze, N, M, next))
{
if (GetPath(maze, N, M, next))
{
return true;
}
}
//左
next = cur;
next.col -= 1;
if (IsPass(maze, N, M, next))
{
if (GetPath(maze, N, M, next))
{
return true;
}
}
//右
next = cur;
next.col += 1;
if (IsPass(maze, N, M, next))
{
if (GetPath(maze, N, M, next))
{
return true;
}
}
//四個(gè)方向都不能走，就出棧返回
StackPop(&path);
return false;
}
void PrintPath(ST* ps)
{
ST rpath;//創(chuàng)建需要導(dǎo)數(shù)據(jù)的另一個(gè)棧
StackInit(&rpath);
while (!StackEmpty(ps))
{
StackPush(&rpath, StackTop(ps));
StackPop(ps);
}
while (!StackEmpty(&rpath))
{
PT cur = StackTop(&rpath);
printf("(%d,%d)\n", cur.row, cur.col);
StackPop(&rpath);
}
StackDestroy(&rpath);
}
int main()
{
int N = 0, M = 0;
scanf("%d %d", &N, &M);
PT cur = { 0,0 };
StackInit(&path);
//動(dòng)態(tài)開辟二維數(shù)組
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]);
}
}
if (GetPath(maze, N, M, cur))
{
PrintPath(&path);
}
StackDestroy(&path);
for (int i = 0; i < N; i++)
{
free(maze[i]);
}
free(maze);
return 0;
}
三、地下迷宮問(wèn)題的思路
看看這個(gè)問(wèn)題：地下迷宮
記錄重點(diǎn)：
- 現(xiàn)在0代表障礙物，1代表通路，并且增加了體力值，左右移動(dòng)減1，上移動(dòng)減3，下移動(dòng)不消耗，如果體力值為0還未到達(dá)出口，將無(wú)法逃離迷宮。
- （0，0）位置為起點(diǎn)，（0，m-1）位置為出口，并且現(xiàn)在要求最后打印的是最短路徑。
- 體力值為0還未到達(dá)出口，結(jié)果需要打?。篊an not escape!
- 坐標(biāo)打印改變變成[0,0],
分析思路：
- 增加體力值P變量，并且當(dāng)判斷四個(gè)方向分別可以通過(guò)時(shí)，同時(shí)傳入?yún)?shù)P，向上方向能通過(guò)傳參數(shù)P-3，向左或者右方向能通過(guò)傳P-1，向下傳P；同時(shí)改變通路為1，出口為（0，m-1）
- 為了找到最短路徑，直接通過(guò)建兩個(gè)棧，一個(gè)記錄當(dāng)前路徑的坐標(biāo)，一個(gè)記錄當(dāng)前為止最短路徑的坐標(biāo)；利用遞歸列出所有可以走的路徑，然后挑出最小的路徑。（下面會(huì)重點(diǎn)介紹如何安全的轉(zhuǎn)移棧以及如何用遞歸找到所有路徑）
- 挑選的路徑也要滿足體力值條件；當(dāng)所有的路徑，體力都會(huì)耗盡且沒有到達(dá)終點(diǎn)，記錄最短路徑坐標(biāo)的棧為空，就可以通過(guò)這個(gè)情況打印Can not escape!。
四、地下迷宮的代碼實(shí)現(xiàn)
先搭建一個(gè)基本的框架。
- 動(dòng)態(tài)創(chuàng)建二維數(shù)組
- 獲得路徑
- 打印路徑
創(chuàng)建體力值，并且改變通路條件、出口、打印和函數(shù)參數(shù)調(diào)用
//
ST path;//可以創(chuàng)局部變量，這里方便一下
bool IsPass(int** maze, int N, int M, PT cur)
{
if (cur.col >= 0 && cur.col < M && cur.row >= 0 && cur.row < N
&& maze[cur.row][cur.col] == 1) //通路條件為1
{
return true;
}
else
{
return false;
}
}
bool GetPath(int** maze, int N, int M, PT cur, int P)
{
//走過(guò)的坐標(biāo)先入棧
StackPush(&path, cur);
//到達(dá)終點(diǎn)
if (cur.row == 0 && cur.col == M - 1) //終點(diǎn)為(0,m-1)
{
return true;
}
//上下左右判斷
PT next;
maze[cur.row][cur.col] = 2;
//上
next = cur;
next.row -= 1;
if (IsPass(maze, N, M, next))
{
if (GetPath(maze, N, M, next, P-3))
{
return true;
}
}
//下
next = cur;
next.row += 1;
if (IsPass(maze, N, M, next))
{
if (GetPath(maze, N, M, next, P))
{
return true;
}
}
//左
next = cur;
next.col -= 1;
if (IsPass(maze, N, M, next))
{
if (GetPath(maze, N, M, next, P-1))
{
return true;
}
}
//右
next = cur;
next.col += 1;
if (IsPass(maze, N, M, next))
{
if (GetPath(maze, N, M, next, P-1))
{
return true;
}
}
//四個(gè)方向都不能走，就出棧返回
StackPop(&path);
return false;
}
void PrintPath(ST* ps)
{
ST rpath;
StackInit(&rpath);
while (!StackEmpty(ps))
{
StackPush(&rpath, StackTop(ps));
StackPop(ps);
}
while (StackSize(&rpath) > 1)
{
PT cur = StackTop(&rpath);
printf("[%d,%d],", cur.row, cur.col);
StackPop(&rpath);
}
//前面打印帶"," 最后一個(gè)不帶
PT cur = StackTop(&rpath);
printf("[%d,%d]\n", cur.row, cur.col);
StackPop(&rpath);
StackDestroy(&rpath);
}
int main()
{
int N = 0, M = 0, P = 0; //體力值P
scanf("%d %d %d", &N, &M, &P);
PT cur = { 0,0 };
StackInit(&path);
//動(dòng)態(tài)開辟二維數(shù)組
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]);
}
}
if (GetPath(maze, N, M, cur, P))
{
PrintPath(&path);
}
StackDestroy(&path);
for (int i = 0; i < N; i++)
{
free(maze[i]);
}
free(maze);
return 0;
}
找到所有的路徑和記錄的實(shí)現(xiàn)：
主要難的是這里的遞歸思想。
- 如果有通路，就移動(dòng)到下一個(gè)坐標(biāo)進(jìn)行四個(gè)方向的判斷，直到體力值用完到達(dá)終點(diǎn)或者沒有到達(dá)終點(diǎn)。
- 到達(dá)終點(diǎn)之后，第一次到達(dá)終點(diǎn)保存這條路徑，之后比較兩條路徑，選最短的路徑；之后回到上一個(gè)坐標(biāo)點(diǎn)
- 到達(dá)終點(diǎn)之后，當(dāng)前坐標(biāo)繼續(xù)進(jìn)行四個(gè)方向的判斷，當(dāng)四個(gè)方向都不能通過(guò)的時(shí)候，為了讓下次能訪問(wèn)這個(gè)坐標(biāo)，將這個(gè)坐標(biāo)恢復(fù)為1，并且返回上一個(gè)坐標(biāo)。
- 每個(gè)可以通過(guò)的坐標(biāo)都將進(jìn)行4個(gè)方向的判斷，當(dāng)所有可通過(guò)坐標(biāo)判斷完成，遞歸函數(shù)結(jié)束。
為什么要?jiǎng)?chuàng)建兩個(gè)棧？
因?yàn)橛幸粋€(gè)棧里面的數(shù)據(jù)是會(huì)變的，所有需要深拷貝一個(gè)棧記錄原來(lái)不變的數(shù)據(jù)。
void StackCopy(ST* path, ST* minpath)
{
minpath->a = (STDataType*)malloc(sizeof(STDataType*) * path->capacity);
memcpy(minpath->a, path->a, sizeof(STDataType) * path->top);
minpath->capacity = path->capacity;
minpath->top = path->top;
}
void GetPath(int** maze, int N, int M, PT cur, int P)
{
StackPush(&path, cur);
//到達(dá)終點(diǎn)
if (cur.row == 0 && cur.col == M - 1)
{
if (P >= 0 && StackEmpty(&minpath) || StackSize(&path) < StackSize(&minpath))
{
StackDestroy(&minpath);
StackCopy(&path, &minpath);
}
}
//上下左右判斷
PT next;
maze[cur.row][cur.col] = 2;
//上
next = cur;
next.row -= 1;
if (IsPass(maze, N, M, next))
{
GetPath(maze, N, M, next, P - 3);
}
//下
next = cur;
next.row += 1;
if (IsPass(maze, N, M, next))
{
GetPath(maze, N, M, next, P);
}
//左
next = cur;
next.col -= 1;
if (IsPass(maze, N, M, next))
{
GetPath(maze, N, M, next, P - 1);
}
//右
next = cur;
next.col += 1;
if (IsPass(maze, N, M, next))
{
GetPath(maze, N, M, next, P - 1);
}
//恢復(fù)
maze[cur.row][cur.col] = 1;
StackPop(&path);
}
完整代碼：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-786314.html
#include<stdio.h>;
#include<stdlib.h>;
#include<assert.h>;
#include<stdbool.h>;
#include<string.h>;
typedef struct position
{
int row;
int col;
}PT;
typedef PT STDataType;
typedef struct stack {
STDataType* a;
int top;
int capacity;
}ST;
void StackInit(ST* ps);
void StackDestroy(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) {
ps->a = NULL;
ps->capacity = 0;
ps->top = 0;//或者-1
}
void StackPush(ST* ps, STDataType x) {
if (ps->capacity == ps->top) {
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * newcapacity);
if (tmp == NULL) {
printf("realloc fail\n");
exit(-1);
}
ps->a = tmp;
ps->capacity = newcapacity;
}
ps->a[ps->top++] = x;
}
void StackDestroy(ST* ps) {
assert(ps);
free(ps->a);
ps->a = NULL;
ps->capacity = ps->top = 0;
}
void StackPop(ST* ps)
{
assert(ps);
/*assert(ps->top > 0);*/
assert(!StackEmpty(ps));
ps->top--;
}
STDataType StackTop(ST* ps)
{
assert(ps);
assert(!StackEmpty(ps));
return ps->a[ps->top - 1];
}
int StackSize(ST* ps)
{
assert(ps);
return ps->top;
}
bool StackEmpty(ST* ps)
{
return ps->top == 0;
}
void StackCopy(ST* path, ST* minpath)
{
minpath->a = (STDataType*)malloc(sizeof(STDataType*) * path->capacity);
memcpy(minpath->a, path->a, sizeof(STDataType) * path->top);
minpath->capacity = path->capacity;
minpath->top = path->top;
}
ST path;
ST minpath;
//判斷通路
bool IsPass(int** maze, int N, int M, PT cur)
{
if (cur.col >= 0 && cur.col < M && cur.row >= 0 && cur.row < N
&& maze[cur.row][cur.col] == 1)
{
return true;
}
else
{
return false;
}
}
//遞歸找到最小路徑
void GetPath(int** maze, int N, int M, PT cur, int P)
{
StackPush(&path, cur);
//到達(dá)終點(diǎn)
if (cur.row == 0 && cur.col == M - 1)
{
if (P >= 0 && StackEmpty(&minpath) || StackSize(&path) < StackSize(&minpath))
{
StackDestroy(&minpath);
StackCopy(&path, &minpath);
}
}
//上下左右判斷
PT next;
maze[cur.row][cur.col] = 2;
//上
next = cur;
next.row -= 1;
if (IsPass(maze, N, M, next))
{
GetPath(maze, N, M, next, P - 3);
}
//下
next = cur;
next.row += 1;
if (IsPass(maze, N, M, next))
{
GetPath(maze, N, M, next, P);
}
//左
next = cur;
next.col -= 1;
if (IsPass(maze, N, M, next))
{
GetPath(maze, N, M, next, P - 1);
}
//右
next = cur;
next.col += 1;
if (IsPass(maze, N, M, next))
{
GetPath(maze, N, M, next, P - 1);
}
maze[cur.row][cur.col] = 1;
StackPop(&path);
}
//打印坐標(biāo)
void PrintPath(ST* ps)
{
ST rpath;
StackInit(&rpath);
while (!StackEmpty(ps))
{
StackPush(&rpath, StackTop(ps));
StackPop(ps);
}
while (StackSize(&rpath) > 1)
{
PT cur = StackTop(&rpath);
printf("[%d,%d],", cur.row, cur.col);
StackPop(&rpath);
}
PT cur = StackTop(&rpath);
printf("[%d,%d]\n", cur.row, cur.col);
StackPop(&rpath);
StackDestroy(&rpath);
}
int main()
{
int N = 0, M = 0, P = 0;
scanf("%d %d %d", &N, &M, &P);
PT cur = { 0,0 };
StackInit(&path);
StackInit(&minpath);
//動(dòng)態(tài)開辟二維數(shù)組
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]);
}
}
//獲得最小路徑
GetPath(maze, N, M, cur, P);
if (!StackEmpty(&minpath))
{
PrintPath(&minpath);
}
else
{
printf("Can not escape!");
}
StackDestroy(&path);
StackDestroy(&minpath);
for (int i = 0; i < N; i++)
{
free(maze[i]);
}
free(maze);
return 0;
}
總結(jié)：迷宮問(wèn)題的難點(diǎn)主要是怎么找到路徑，如何打印路徑坐標(biāo)。如果能解決這些問(wèn)題，那么對(duì)遞歸的理解以及棧的應(yīng)用有很大的提升。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-786314.html
到了這里，關(guān)于【C數(shù)據(jù)結(jié)構(gòu)】迷宮問(wèn)題的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
