回溯问题三:迷宫问题
程序员文章站
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;
}
上一篇: DFS走迷宫
下一篇: 微信小程序去除左上角返回的按钮