首页 > 代码库 > 迷宫问题

迷宫问题

数据结构中一道关于栈与深搜(DFS)的问题。

迷宫有一个入口,一个出口。一个人从入口走进迷宫,目标是找到出口。阴影部分和迷宫的外框为墙,每一步走一格,每格有四个可走的方向,探索顺序为地图方向:南(下)、东(右)、北(上)、西(左)。

输入:输入迷宫数组。第一行数据表示一个 n*n (n<=100)的迷宫;第二行开始的n行为迷宫数据。
其中:0表示路,1表示墙,起点在左上角 <1,1> 的位置,终点在右下角 <n,n> 的位置。

输出:若有解,输出从入口到出口的一条路径,否则输出 there is no solution!

例(上图所示的迷宫数组)

输入:
4 4
0 0 1 0
0 1 0 1
0 0 0 0
0 1 0 0

输出:<1,1> <2,1> <3,1> <3,2> <3,3> <4,3> <4,4> 

#include <stdio.h>

typedef struct
{
    char x, y;
}pos;

pos stack[200];
int top = 0;

char map[102][102] = {0};

void push(char a, char b)
{
    stack[top].x = a;
    stack[top++].y = b;
    map[a][b] = 2;//记得剪枝
}

int main()
{
    int m, n, i, j;
    scanf("%d%d",&m, &n);
    for (i=0; i<=m+1; i++)
        for (j=0; j<=n+1; j++)
            if (i*j>0 && i<=m && j<=n)
                scanf("%d",&map[i][j]);
            else
                map[i][j] = 2;
    if (map[1][1] == 1)
    {
        printf("There is no solution!\n");
        return 0;
    }
    push(1,1);
    while (1)
    {
        if (top == 0)
        {
            printf("There is no solution!\n");
            return 0;
        }
        i = stack[top-1].x;
        j = stack[top-1].y;
        if (i==m && j==n)
        {
            break;
        }
        if(map[i+1][j] == 0)
        {
            push(i+1, j);
            continue;
        }
        else if (map[i][j+1] == 0)
        {
            push(i, j+1);
            continue;
        }
        else if (map[i-1][j] == 0)
        {
            push(i-1, j);
            continue;
        }
        else if (map[i][j-1] == 0)
        {
            push(i, j-1);
            continue;
        }
        top --;
    }
    for (i=0; i<top; i++)
    {
        printf("<%d,%d> ",stack[i].x, stack[i].y);
    }
    printf("\n");
    return 0;
}

 

 没有用C++中的栈,为了输出路径方便,但逻辑上不允许这样做。

迷宫问题