欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

回溯问题三:迷宫问题

程序员文章站 2022-05-20 21:35:40
...

题意:
0 0 0 0 1
1 0 0 0 1
1 0 1 0 1
1 0 1 1 1
1 0 0 1 1
上面矩阵表示一个迷宫,其中的1表示墙壁,0表示可以走的路,现在编写程序从(0,0)开始走从最后一行有出口处走出

解题方法:回溯法,与全排列、地图涂色如出一辙

#include <stdio.h>
#define N 5 //迷宫大小
int Maze[N][N] =
{
    {0,0,0,0,1},
    {1,0,0,0,1},
    {1,0,1,0,1},
    {1,0,1,1,1},
    {1,0,0,1,1}
};
int direction[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};   //四个方向,上下左右,每个方向x、y的增量
int count = 0;//记录方案数

int Check(int i, int j)  //判断下一步是不是通路
{
    if(i >= 0 && i<=4 && j >= 0 && j <= 4)
    {
        if(0 == Maze[i][j])
        {
            return 1;
        }
    }
    return 0;
}

void Find(int ci, int cj)
{
    int n;
    if(N-1 == ci) //到了最后一行,先搞定,再输出
    {
        Maze[ci][cj] = 6;
        printf("\n解法%d:\n", ++count);
        int i, j;
        for(i=0; i<N; ++i)
        {
            for(j=0; j<N; ++j)
            {
                printf("%d ", Maze[i][j]);
            }
            printf("\n");
        }
        Maze[ci][cj] = 0;
    }
    else
    {
        for(n=0; n<4; ++n)///四个方向
        {
            if(Check(ci+direction[n][0], cj+direction[n][1])) //依然用Check实现判断:是否可以在某个方向走下一步
            {
                Maze[ci][cj] = 6;   //6表示走过的路
                Find(ci+direction[n][0], cj+direction[n][1]);
                Maze[ci][cj] = 0;   //回溯恢复值,与全排列、地图涂色等回溯恢复原理一样
            }
        }
    }
}

int main(void)
{
    printf("\n--------------------迷宫问题(1表示墙壁 0 道路 6 路径)--------------------\n\n");
    //(0, 0)为起点
    printf("原始迷宫:\n");
    int i, j;
    for(i=0; i<N; ++i)
    {
        for(j=0; j<N; ++j)
        {
            printf("%d ", Maze[i][j]);
        }
        printf("\n");
    }
    printf("\n");
    Find(0, 0);

    return 0;
}
相关标签: 迷宫问题