问题描述:
设有一个m*n的迷宫,入口在(1, 1),出口在(m, n),迷宫每个格子中分别放有0或1,1表示墙,有障碍,不能走,0表示通路,可以走。迷宫走的规则为上、下、左、右四个方向,且不能回走已经走过的格子。当迷宫地图给出后,求从入口到出口的方案总数,并输出每个方案的路径。
输入格式:
第一行两个整数m,n,表示迷宫有m行n列。
以下m行,每行n个整数(0或1),表示迷宫。
输出格式:
前sum行,每行表示一条路径
第sum+1行,输出一个整数sum,表示方案总数。

输入样例1:
3 4
0 0 0 1
0 1 0 0
0 1 0 0
输出样例1:
(1, 1) (1, 2) (1, 3) (2, 3) (3, 3) (3, 4)
(1, 1) (1, 2) (1, 3) (2, 3) (2, 4) (3, 4)
2

输入样例2:
3 7
0 0 0 1 0 0 1
0 1 0 0 0 0 1
1 0 0 0 1 0 0
输出样例2:
(1, 1) (1, 2) (1, 3) (2, 3) (3, 3) (3, 4) (2, 4) (2, 5) (2, 6) (3, 6) (3, 7)
(1, 1) (1, 2) (1, 3) (2, 3) (3, 3) (3, 4) (2, 4) (2, 5) (1, 5) (1, 6) (2, 6) (3, 6) (3, 7)
(1, 1) (1, 2) (1, 3) (2, 3) (2, 4) (2, 5) (2, 6) (3, 6) (3, 7)
(1, 1) (1, 2) (1, 3) (2, 3) (2, 4) (2, 5) (1, 5) (1, 6) (2, 6) (3, 6) (3, 7)
4

手工栈实现:

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

void push(int x, int y, int d);
void pop(int x, int y);

tydef struct Stack{
    int x, y;
    int d;//d表示方向 上下左右
} Stack;

int m, n, i, j, sum;//sum为方案总数
int maze[100][100], mark[100][100];//maze保存地图,mark标记是否走过
int dx[4] = {1, 0, 0, -1};//下 右 左 上
int dy[4] = {0, 1, -1, 0};
Stack stack[100];
int top;
int x, y, d, px, py; //临时变量

void push(int x, int y, int d)
{
    top += 1;
    stack[top].x = x;
    stack[top].y = y;
    stack[top].d = 0;
    stack[top-1].d = d;
    mark[x][y] = 1;
}

void pop(int x, int y)
{
    stack[top].x = 0;
    stack[top].y = 0;
    stack[top].d = 0;
    top -= 1;
    mark[x][y] = 0;
}

int main()
{
    memset(maze, 1, sizeof(maze));//数组元素初始化为1
    memset(mark, 0, sizeof(mark));
    memset(stack, 0, sizeof(stack));
    scanf("%d %d", &m, &n);
    for (i=1; i<=m; i++)
        for (j=1; j<=n; j++)
            scanf("%d", &maze[i][j]);
    sum = 0;
    top = 0;
    push(1, 1, 0);
    while (top>0)//栈非空
    {
        x = stack[top].x;
        y = stack[top].y;
        d = stack[top].d;
        if ((x==m)&&(y==n))//到达出口
        {
            sum += 1;//方案总数+1
            for (j=1; j<=top; j++)//输出路径
                printf("(%d, %d) ", stack[j].x, stack[j].y);
            printf("\n");
            d = 4;
        }
        while (d<=3)
        {
            px = x + dx[d];
            py = y + dy[d];
            if ((px>=1)&&(py>=1)&&(px<=m)&&(py<=n)&&(maze[px][py]==0)&&(mark[px][py]==0))//这个方向可以通过
            {   
                push(px, py, d+1);
                break;
            }
            d += 1;
        }
        if (d>3)//四个方向都不可行,回溯
        {
            pop(x, y);
        }
    }
printf("%d\n",sum);
}

系统栈实现(dfs深度优先搜索):

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

int x, y, m, n, i, j;
int sum = 0, len = 0;
int maze[100][100], mark[100][100];
int line[100][2]; //save the route 
int dx[4] = {1, 0, 0, -1};//down, right, left, up
int dy[4] = {0, 1, -1, 0};

void find(int x, int y)
{
    int i, j;
    int px, py;
    for (i=0; i<=3; i++)
    {
        px = x + dx[i];
        py = y + dy[i];
        if (maze[px][py]==0 && mark[px][py]==0 && px<=m && py<=n && px>0 && py>0)
        {
            mark[px][py] = 1;
            len += 1;
            line[len][0] = px;
            line[len][1] = py;
            if (px==m && py==n) 
            {
                sum++;
                for (j=0; j<=len; j++)
                    printf("(%d, %d) ",line[j][0], line[j][1]);
                printf("\n");
                len -= 1;
                mark[m][n] = 0;
            }
            else 
            {
                find(px, py);
                mark[px][py] = 0;
                len -= 1;
            }
        }
    }
}


int main()
{
    scanf("%d %d", &m, &n);
    memset(maze, 1, sizeof(maze));//1 is barrier, 0 is avalible
    memset(mark, 0, sizeof(mark));
    memset(line, 0, sizeof(line));
    for (i=1; i<=m; i++)
        for (j=1; j<=n; j++)
            scanf("%d", &maze[i][j]);
    line[0][0] = 1;
    line[0][1] = 1;
    mark[1][1] = 1;
    find(1,1);
    printf("%d\n", sum);
}

小作业:
哈~~~是不是很有趣呢~~~但是我们的栈用数组实现,占用的空间大并且容易造成浪费,所以智宝宝计算一下这两个程序静态空间的大小以及时间空间复杂度~~~并且把它改为更优的链表实现哦~~~么么哒~~~