c语言回溯法迷宫问题

1.题目描述

定义一个二维数组N*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示：

int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为[0,0],既第一空格是可以走的路。

2.源码实现

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

void MazeTrack(int **maze, int x, int y, int a, int b, int r, int s, int m, int *u, int *v)
{
    int i;

    u[2*m] = x;
    u[2*m+1] = y;

    maze[x][y] = 1;

    if(x == a && y == b)
    {
        if(v[0] != -1)
        {
            if(m + 1 < v[0])
            {
                v[0] = m + 1;

                for(i=0; i<v[0]; i++)
                {
                    v[2*i+1] = u[2*i];
                    v[2*i+2] = u[2*i+1];
                }
            }
        }
        else
        {
            v[0] = m + 1;

            for(i=0; i<v[0]; i++)
            {
                v[2*i+1] = u[2*i];
                v[2*i+2] = u[2*i+1];
            }
        }
    }

    /*可以向左走*/
    if((x-1) >= 0 && maze[x-1][y] == 0)
    {
        MazeTrack(maze, x-1, y, a, b, r, s, m+1, u, v);
    }

    /*可以向右走*/
    if((x+1) < r && maze[x+1][y] == 0)
    {
        MazeTrack(maze, x+1, y, a, b, r, s, m+1, u, v);
    }

    /*可以向上走*/
    if((y-1) >= 0 && maze[x][y-1] == 0)
    {
        MazeTrack(maze, x, y-1, a, b, r, s, m+1, u, v);
    }

    /*可以向下走*/
    if((y+1) < s && maze[x][y+1] == 0)
    {
        MazeTrack(maze, x, y+1, a, b, r, s, m+1, u, v);
    }

    maze[x][y] = 0;
}

int main()
{
    int maze[10][10];
    int u[2][100];
    int *w[10];
    int n, m;
    int i, j;

    for(i=0; i<10; i++)
    {
        w[i] = maze[i];
    }

    while(scanf("%d %d", &n, &m) != EOF)
    {
        u[1][0] = -1;

        /*printf("n=%d, m=%d\n", n, m);*/

        for(i=0; i<n; i++)
        {
            for(j=0; j<m; j++)
            {
                scanf("%d", &maze[i][j]);
            }
        }

        /*printf("n=%d, m=%d\n", n, m);*/

        MazeTrack(w, 0, 0, n-1, m-1, n, m, 0, u[0], u[1]);

        for(i=0; i<u[1][0]; i++)
        {
            printf("(%d,%d)\n", u[1][2*i+1], u[1][2*i+2]);
        }
    }

    return 0;
}

3.编译源码

$ gcc -o example examle.c -std=c89

4.运行及其结果

$ ./example
5 5
0 1 0 0 0
0 1 0 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)