如图，有如此的一个迷宫，要从起点到终点，紫色方格是障碍物方格，不可通行。
求：
找出一条从起点到终点的道路，在到达终点之前，必须走遍所有可通行的方格一次，而且到达终点的
转弯次数要最少，每改变一次前进方向算作转弯一次。
经典的回溯法解题思路：
1 //方格m*n,k个障碍物
2 int m,n,k;
3 //目标方格
4 int dx,dy;
5 //当前拐弯数，最右拐弯数
6 int dirs,best;
7 //总共找到几条路线
8 int count;
9
10 void search(int depth,int x,int y,int di)
11 {
12 if(depth==m*n-k && dx==x && dy==y && )
13 {
14 //找到一条路线
15 count++;
16
17 if(dirs<best)
18 {
19 best=dirs;
20 //保存最优路径，即标记不为0的方格
21 save();
22 }
23 else
24 {
25 return;
26 }
27 }
28 else
29 {
30 for(int i=1;i<=8;i++)
31 {
32 if(没有出边界 && 该方格未行走过)
33 {
34 board[x+dx[i]][y+dy[i]]=depth+1;
35 if(di!=i) dirs++;
36 search(depth+1,x+dx[i],y+dy[i],i);
37 //恢复转弯次数
38 if(di!=i) dirs--;
39 //恢复未行走标记
40 board[x+dx[i]][y+dy[i]]=0;
41 }
42 }
43 }
44
45 }
看上去挺复杂的问题，用回溯法可以很好地解决，还可以加入剪枝函数，即检测当前dirs是否已经大于best，如果
是的话，直接返回。
posted on 2010-08-12 16:07
野猪红 阅读(1184)
评论(0) 编辑 收藏 引用 所属分类:
算法 、
Show Demo