C 语言—中级迷宫问题

题目要求:
C 语言—中级迷宫问题

运行结果：

'3’为走过的路径，程序有一定的缺陷，只能找出一条路，其他的没有问题，思路在注释中写的很详细，欢迎大家指教！
/************************************************************************
*      文件名：maze
*      文件功能描述：迷宫问题
*      文件作者名：Mr_han QQ:785937095
*      说明：
*       1、定义一个二维数组N*M（其中2<=N<=10;2<=M<=10）
*       2、它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。
*       3、一个N × M的二维数组，表示一个迷宫。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。
**************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define LONG long
#define CHAR char

LONG N, M, sum = 0;

void Maze( LONG buf[][M] )
{
    LONG i, j, a, b, c, d;
    i = j = 0;
    LONG m[50]    = {0};               /*用来记录路径坐标*/
    LONG n[50]    = {0};               /*用来记录每个路口*/
    LONG x = 0;
    while ( i < N && j < M )           /*若没有到达迷宫末尾则一直循环*/
    {
        buf[i][j] = 3;                 /*将走过的位置都用3来替换，以免重复*/
        m[2*sum]   = i;                /*按步数存储坐标，当遇到死路返回时步数减少，重新存储路径坐标*/
        m[2*sum+1] = j;
        if( N - 1 == i && M - 1 == j ) /*到达迷宫末尾跳出循环*/
        {
            goto OVER;
        }
        a = b = c = d = 1;             /*定时四个标志位，表示可走的路有几条，有几条可以走就将对应的标志位置0*/

        if ( M > (j + 1) && 0 == buf[i][j+1] )
        {
            a = 0;
        }
        if ( N > (i + 1) && 0 == buf[i+1][j] )
        {
            b = 0;
        }
        if ( 0 < j && 0 == buf[i][j-1] )
        {
            c = 0;
        }
        if ( 0 < i && 0 == buf[i-1][j] )
        {
            d = 0;
        }
        if ( 3 > a + b + c + d )        /*若该点有多条路可走，则记录该位置，可以记录所有的路口*/
        {
            n[x] = sum;                 /*记录在该路口时走过的步数，方便遇到死路后回到该点，路数改变也方便路径坐标的存储*/
            x++;
        }


        if ( 0 == a )      { j += 1; }  /*右*/
        else if ( 0 == b ) { i += 1; }  /*下*/
        else if ( 0 == c ) { j -= 1; }  /*左*/
        else if ( 0 == d ) { i -= 1; }  /*上*/

        sum++;                          /*移动后步数加1*/
        if ( 4 == a + b + c + d )       /*遇到死路，则返回上个路口*/
        {
            x--;
            sum = n[x];
            i = m[2*sum];               /*获取在走sum步时的横坐标*/
            j = m[2*sum+1];             /*获取在走sum步时的纵坐标*/
        }
    }
OVER:
    for ( i = 0; i < N; i++ )           /*打印地图，方便观察对比*/
    {
        for ( j = 0; j < M; j++ )
        {
            printf ( "%d ",buf[i][j] );
        }
        puts("");
    }

    printf ( "数字‘3’ 为路径，有效步数共 %d 步\n", sum );

    for ( i = 0; i <= sum; i++ )
    {
        printf ( "(%d, %d) ", m[2*i],m[2*i+1] );   /*打印路径*/
    }

    return;
}

void main()
{
    N = M = 8;
    /*scanf ( "%d %d",&N,&M ); 我的编辑器版本较低，不能使用变量定义数组 */
    LONG buf[8][8] = {          /*本应是buf[N][M] 但只有在最新的c规范中，数组定义才可以用变量，故只能手动去修改数组大小*/
        0, 1, 1, 1, 0, 1, 1, 0,
        0, 0, 0, 0, 0, 0, 1, 0,
        1, 1, 0, 1, 0, 1, 1, 0,
        0, 1, 0, 1, 0, 0, 1, 0,
        0, 0, 0, 1, 1, 1, 1, 0,
        0, 1, 1, 1, 0, 1, 1, 0,
        0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 1, 1, 0};

    Maze( buf );

    return;
}
C 语言—中级 迷宫问题

相关推荐

C 语言—中级迷宫问题
