C语言递归回溯法迷宫求解

本例将随机产生一个10*10的迷宫输出后，在下面输出此迷宫的解法。解法为从坐标（1，1）处进入，从（8，8，）出去，优先线路为先右后下再上最后为左。不少人求解此题时运用的栈的相关知识，本例寻找线路的过程不运用进栈出栈，而是用回溯法“抹去”判断不行的线路。话不多说，上代码。#include <stdio.h>#include <stdlib.h>#include <time.h>//包括根据当前时间产生随机数的函数static int maze[10][10];//创建迷宫int creatmaze（）{srand（（unsigned）time（NULL））;for（int i=0; i<10; i++）{for（int j=0; j<10; j++）{if（（i==1&&j==1）||（i==8&&j==8））maze[i][j]=0;elsemaze[i][j]=rand（）%3;//为保证墙的数目较少，产生的随机数1为墙，0和2为路if（maze[i][j]==2）maze[i][j]=0;if（maze[i][j]==1||i==0||i==9||j==0||j==9）//迷宫框架为墙{maze[i][j]=1;printf（" O "）;}elseprintf（" "）;}printf（" "）;}printf（" "）;}//输出线路（结果）void printroute（）{for（int i=0; i<10; i++）{for（int j=0; j<10; j++）{if（maze[i][j]==1）printf（" O "）;else if（maze[i][j]==0）printf（" "）;else if（maze[i][j]==2）printf（" X "）;}printf（" "）;}}//寻找线路void findroute（int i,int j）{if（i==8&&j==8）//边界条件，即找到出路{printroute（）;exit（0）;}else{if（maze[i][j+1]！=1&&maze[i][j+1]！=2）//判断当前位置右边是否为墙（下同理）{maze[i][j]=2;//将2作为线路的标志j++;findroute（i,j）;//递归j--;//回溯maze[i][j]=0;}if（maze[i+1][j]！=1&&maze[i+1][j]！=2）//下{maze[i][j]=2;i++;findroute（i,j）;i--;maze[i][j]=0;}if（maze[i-1][j]！=1&&maze[i-1][j]！=2）//上{maze[i][j]=2;i--;findroute（i,j）;i++;maze[i][j]=0;}if（maze[i][j-1]！=1&&maze[i][j-1]！=2）//左{maze[i][j]=2;j--;findroute（i,j）;j++;maze[i][j]=0;}if（i==1&&j==1&&maze[1][2]==1&&maze[2][1]==1）//此处用于判断入口右方和下方是否为通路，若两处均有墙则直接输出无路{printf（"no way "）;exit（0）;}}}int main（）{creatmaze（）;findroute（1,1）;printf（"no way "）;//没有找到出路} 样例输出：本文永久更新链接地址：http://www.linuxidc.com/Linux/2017-01/139480.htm