迷宫问题——回溯法解

作者:北京诚信汇发物流有限公司  来源:www.cxhfwL.com  发布时间:2017-09-03 12:37:15
迷宫问题——回溯法解

迷宫是一个二维矩阵,其中1为墙,0为路,入口在第一列,出口在最后一列。
要求从入口开始,从出口结束,按照 上,下,左,右 的顺序来搜索路径.

输入

第一行输入迷宫大小N
第二行输入入口坐标
接下来n行输入完整迷宫

输出

输出完整棋盘,所有解法,走过的路用6表示。

样例输入 8 0 7 1 1 1 1 1 1 1 1 1 0 1 1 0 0 0 0 1 0 1 0 0 1 0 1 1 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 1 0 0 0 0 1 1 1 1 0 1 0 0 1 0 1 0 0 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 样例输出 1 1 1 1 1 1 1 1 1 0 1 1 6 6 6 6 1 0 1 6 6 1 0 1 1 1 6 6 1 0 1 1 1 6 6 1 0 0 0 1 1 6 0 0 0 1 1 1 1 6 1 0 0 1 0 1 6 6 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 实现代码 #include #define N 19 //整个迷宫大小(包括最外层墙壁) char Maze[N][N] = { {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0}, {1,1,1,0,1,1,1,0,1,0,1,1,1,1,1,0,1,1,1}, {1,0,0,0,0,0,1,0,1,0,0,0,0,0,1,0,0,0,1}, {1,1,1,0,1,0,1,0,1,1,1,1,1,0,1,1,1,1,1}, {1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,0,0,1}, {1,0,1,0,1,1,1,0,1,1,1,0,1,1,1,1,1,0,1}, {1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,1}, {1,0,1,1,1,1,1,1,1,1,1,0,1,0,1,1,1,1,1}, {1,0,1,0,0,0,0,0,0,0,1,0,1,0,1,0,0,0,1}, {1,0,1,0,1,1,1,0,0,0,1,0,1,0,1,0,1,0,1}, {1,0,0,0,1,0,0,0,0,0,1,0,1,0,0,0,1,0,1}, {1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1}, {1,0,1,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,1}, {1,0,1,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1}, {1,0,1,0,1,0,0,0,1,0,0,0,1,0,1,0,1,0,1}, {1,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,1,0,1}, {0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,1}, {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1} }; char step[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; //定义四个方向 int count = 0; char Check(char i, char j) //判断下一步是不是通路 { if(i >= 0 && i<=18 && j >= 0 && j <= 18) { if(0 == Maze[i][j]) { return 1; } } return 0; } void Display(void) { char i, j; for(i=0; i

企业建站2800元起,携手武汉肥猫科技,做一个有见地的颜值派!更多优惠请戳:荆州SEO http://jingzhou.4567w.com


上一篇:Python - 文本处理模块
下一篇:最后一页