Question

【迷宫问题】用堆栈解迷宫

我们c语言实践课的题目，我实在编不出来，求助。。
题目：有一个40*60的迷宫，0和1分别表示迷宫中的通路和障碍，设计一个程序,对任意设定的迷宫，求出一条从入口到出口的通路，或得出没有通路的结论。
对于本问题需用栈实现“穷举求解”算法，即：从入口出发，顺着某一个方向进行探索，若能走通，则继续往前进；否则沿着原路退回，换一个方向继续探索，直至出口位置，求得一条通路。加入所有可能的通路都探索到而未能到达出口，则所设定的迷宫没有通路。迷宫数据用二维数组存储，起点为（1,1），终点为（40,60），对于迷宫中每个数据都有四个方向可通。
我们老师给了一个写好的库
#include<malloc.h>
typedef char DATA_TYPE;
struct Stack
{
DATA_TYPE *data;
int top;
int capacity;
};

int InitStack(Stack* s,int size=100)
{
s->data = (DATA_TYPE*)malloc(size*sizeof(DATA_TYPE));

if(s->data == NULL) //如果空间动态非配出错，就报错
return 0;

s->capacity = size;
s->top = 0;
return 1;
}

int IsFull(Stack* s)
{
if(s->top >= s->capacity)return 1;
else return 0;
}

int IsEmpty(Stack *s)
{
if(s->top <= 0)return 1;
else return 0;
}

int Push(Stack *s ,DATA_TYPE d)
{
if(IsFull(s))return 0;
else
{
s->data[s->top++]=d;
return 1;
}
}

int Pop(Stack* s,DATA_TYPE &d)
{
if(IsEmpty(s))
return 0;
else
{
s->top--;
d=s->data[s->top];
return 1;
}
}

int GetTop(Stack*s,DATA_TYPE &d)
{
if(IsEmpty(s))return 0;
else
{
d = s->data[s->top-1];
return 1;
}
}

int ClearStack(Stack* s)
{
s->top=0;
return 1;
}

int DestoryStack(Stack* s)
{
delete[] s->data;
s->top=-1;
s->capacity=-1;
return 1;
}

还给了思路，据他说把这思路翻译成程序语言就行，很简单的。。。简单的。。。单的。。。我知道这样都写不出来真的好废，但是还是没牙的来求助了(*+﹏+*)~
1、假设P为当前点
2、如果P为出口，则结束循环
3、检查当前点P是否有路可走，
如果有，则将P点状态打包存入堆栈，让出路上的点成为当前点P
如果没有，则将堆栈弹出，让栈顶节点成为当前点P
4、跳转2，继续循环

Answer 1

#include <stdio.h>
#include <time.h>
#include <stdlib.h>
#include <string.h>


#define MAXM 40  
#define MAXN 60
int maze[MAXM][MAXN]; // 0 1-障碍物
int m = 40, n = 60; // 40行60列
int used[MAXM][MAXN]; // 记录是否到过


int line[MAXM*MAXN]; // 记录迷宫路线
int line_len;
int line_r[MAXM*MAXN];

int d[4][2] = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1} }; // 4个方向

void dfs(int u, int v, int step)
{
    int x, y, i;
    if (line_len != 0)
        return;
    if (u == m-1 && v == n-1)
    {
        line_len = step;
        memcpy(line_r, line, line_len*sizeof(int));
        return;
    }

    for (i = 0; i < 4; i++)
    {
        x = u + d[i][0];
        y = v + d[i][1];
        if (x >= 0 && x < m && y >= 0 && y < n && !used[x][y] && maze[x][y]==0)
        {
            used[x][y] = 1;
            line[step] = x << 16 | y;
            dfs(x, y, step+1);
            // used[x][y] = 0; // 不用退回来了，因为只需要一条路径
        }
    }
}

int main() 
{
    int i, j;
    // 随机生成迷宫
    srand(time(NULL));
    for (i = 0; i < m; i++)
        for (j = 0; j < n; j++)
            maze[i][j] = rand()%8 == 0 ? 1 : 0; // 是1的概率约1/8,通路的概率大些
    maze[0][0] = maze[m-1][n-1] = 0; // 起始点和终端必须为0

    line_len = 0;
    line[0] = 0 << 16 | 0;
    memset(used, 0, sizeof(used));
    dfs(0, 0, 0); // (0,0) -> (m-1, n-1)

    if (line_len == 0)
        printf("没有通路\n");
    else
    {
        for (i = 0; i < line_len; i++)
            printf("( %d, %d )\n", (line_r[i]>>16)+1, (line_r[i]&0xffff)+1);
    }

    return 0;
}

 你给的那库实在是没什么用的欲望，要最短路径一般用广度搜索，上面的代码应该属于深度搜索

追问

那个库不能用吗。。据说好像只会用到push和pop什么的。。迷宫也是他做好的txt文件，用二进制读入到二维数组就行。。
我真是太渣了你写的有点看不懂QAQ我们要跟老师解释程序的、不用那个库看着不像自己写的说~>_<~

追答

库里面的内容用处不大，封装成一堆无用函数（说的直白了点，勿怪）
要用是替换代码里的line数组，存储结果用的