前言
思路介绍中省略了关于如何进行回溯搜索的细节，而主要讨论回溯中所使用的剪枝策略。
题
对于如图7×7的网格，从左上角开始到右下角结束遍历所有的方块仅一次，总共有多少种不同的遍历路径？
思路
基本思路：回溯法进行搜索。但纯暴力的搜索时间复杂度太大，需要加上剪枝的优化。
剪枝：可剪掉会导致不连通的走法，每走一步都判断是否联通。例如下图中的第五步，就将网格划分成了两片不连通的区域。
判断联通性，思路1：
for 格子 in 所有网格 if(以该格子作为起点进行搜索，能找到一条到达终点的路径) 该格子与终点联通 if(所有格子都与终点联通) 所有网格之间是联通的
即在一次是否联通的判断中，对应每个空的（没走过的）格子都进行一次回溯搜索。
到这里可能就会疑惑，剪枝的代价这么大，值得吗？答案是值得的，可以自己写有剪枝和纯暴力的程序对比一下。
看似一下只剪掉了一种情况，有时其实剪掉的相连的枝条是非常多的。
剪枝效果：对题中 7 * 7 的网格，程序需要运行 2~3 分钟才能得到结果（毕竟搜索的基数还是太大了）。然而比纯暴力的情况好很多（纯暴力搜索我根本没看到结果）。
判断联通性，思路2：
前面的剪枝虽然有一些效果（至少可以看得见结果），然而每次剪枝代价还是偏大。每次判断联通，都对每个格子应用一次回溯搜索其实是不必要的。
那是一种比较静态的思路，你给我一张网格，告诉我哪些格子走过了（被覆盖），哪些格子没走过（空白），然后我告诉你它是不是联通。
另一种想法，就是考虑怎样走会导致不连通，因为状态从联通到不连通的转变只在某一步。
要把一块区域困死，走的路径就肯定会形成闭环，可以作以下断言：
if(我某一步后，前方是墙壁或走过的格子，且此时我两边都是没走过的格子） 不连通 else 联通
对剪枝进行优化后，仅需 2~3 秒即得到结果。
实现（C++）
思路1
#include<iostream> using namespace std; const int Len = 7;//迷宫的边长 //-------------------------------------------------- //复制一个二维数组，将在live()中被调用 void copy_mg(int source[][Len], int target[][Len]){ for(int i = 0; i < Len; i++){ for(int j = 0; j < Len; j++){ target[i][j] = source[i][j]; } } } //-------------------------------------------------- //判断位置(y,x)是否仍与终点联通 bool chance(int mg[][Len], int y, int x){ //出来了吗？ if(y == Len-1 && x == Len-1){ return true; } //1 if(y < Len - 1) { mg[y][x] = '#'; y++; if(mg[y][x] == 0){ if(chance(mg, y, x)){ return true; } } y--; mg[y][x] = 0; } //2 if(y > 0) { mg[y][x] = '#'; y--; if(mg[y][x] == 0){ if(chance(mg, y, x)){ return true; } } y++; mg[y][x] = 0; } //3 if(x < Len - 1) { mg[y][x] = '#'; x++; if(mg[y][x] == 0){ if(chance(mg, y, x)){ return true; } } x--; mg[y][x] = 0; } //4 if(x > 0) { mg[y][x] = '#'; x--; if(mg[y][x] == 0){ if(chance(mg, y, x)){ return true; } } x++; mg[y][x] = 0; } return false; } //-------------------------------------------------- //判断是否存在点被困死，未困死返回true bool live(int maze[][Len]){ for(int i = 0; i < Len; i++){ for(int j = 0; j < Len; j++){ if(maze[i][j] > 0) continue; int mg[Len][Len] = {}; copy_mg(maze, mg); bool t = chance(mg, i, j); if(! t){ return false; } } } return true; } //-------------------------------------------------- //打印迷宫路径 void printMaze(int maze[][Len]){ for(int i = 0; i < Len; i++){ for(int j = 0; j < Len; j++){ printf("(%3d) ", maze[i][j]); } cout<<endl; } cout<<endl; } //-------------------------------------------------- //参数y为行标，x为列标 void road(int maze[][Len], int y, int x, int & count, int num){ num++; //不符合继续递归条件的情况：1、走到了墙上2、有点被困死再无法走到 if(maze[y][x] > 0 || live(maze) == 0){ return; } //到达终点 if(x == Len-1 && y == Len-1){ maze[y][x] = num; //判断是否走过了所有的点 if(maze[y][x] == Len * Len){ count++; if(count % 10000 == 0) { cout<<"count: "<<count<<" (y,x): "<<y<<" "<<x<<endl; printMaze(maze); } } maze[y][x] = 0; return; } //上 if(y - 1 >= 0){ maze[y][x] = num; road(maze, y-1, x, count, num); maze[y][x] = 0; } //下 if(y + 1 < Len){ maze[y][x] = num; road(maze, y+1, x, count, num); maze[y][x] = 0; } //左 if(x - 1 >= 0){ maze[y][x] = num; road(maze, y, x-1, count, num); maze[y][x] = 0; } //右 if(x + 1 < Len){ maze[y][x] = num; road(maze, y, x+1, count, num); maze[y][x] = 0; } } //-------------------------------------------------- int main(){ int maze[Len][Len] = {}; int count = 0;//路径的数量 road(maze, 0, 0, count, 0); cout<<"result:"<<count<<endl; return 0; }
思路2
//1.剪枝：不连通 #include<iostream> using namespace std; const int Len = 7;//迷宫的边长 //-------------------------------------------------- //判断走当前这一步是否会导致不连通 bool live(int maze[][Len], int y, int x){ //上下堵，左右空 if((y+1 >= Len || maze[y+1][x] != 0) && (y-1 < 0 || maze[y-1][x] != 0)){ if(x-1 >= 0 && maze[y][x-1] == 0 && x+1 < Len && maze[y][x+1] == 0){ return false; } } //左右堵，上下空 else if((x+1 >= Len || maze[y][x+1] != 0) && (x-1 < 0 || maze[y][x-1] != 0)){ if(y-1 >= 0 && maze[y-1][x] == 0 && y+1 < Len && maze[y+1][x] == 0){ return false; } } return true; } //-------------------------------------------------- //参数y为行标，x为列标 void road(int maze[][Len], int y, int x, int & count, int num){ //(y,x):当前坐标，count:路径总数，num:当前是第多少步 num++; //不符合继续递归条件的情况：1、走到了墙上2、有点被困死再无法走到 if(maze[y][x] > 0 || live(maze, y, x) == 0){ return; } //到达终点 if(x == Len-1 && y == Len-1){ maze[y][x] = num; //判断是否走过了所有的点 if(maze[y][x] == Len * Len){ count++; } maze[y][x] = 0; return; } //上 if(y - 1 >= 0){ maze[y][x] = num; road(maze, y-1, x, count, num); maze[y][x] = 0; } //下 if(y + 1 < Len){ maze[y][x] = num; road(maze, y+1, x, count, num); maze[y][x] = 0; } //左 if(x - 1 >= 0){ maze[y][x] = num; road(maze, y, x-1, count, num); maze[y][x] = 0; } //右 if(x + 1 < Len){ maze[y][x] = num; road(maze, y, x+1, count, num); maze[y][x] = 0; } } //-------------------------------------------------- int main(){ int maze[Len][Len] = {}; int count = 0;//路径的数量 road(maze, 0, 0, count, 0); cout<<"result:"<<count<<endl; return 0; }
bug记录
在写live()函数时，我一开始的 if 语句如下。只有当前位置的上方或下方不是空格子，就判断为“碰到墙壁”。
//向上碰壁或向下碰壁 if(y+1 >= Len || maze[y+1][x] != 0 || y-1 < 0 || maze[y-1][x] != 0)
但后面发现，我给live()这个函数并没有传递“这一步是向哪个方向走达到的”这个方向信息，要判断碰壁应改为下面的代码（碰壁时，来的方向和走向的方向肯定都不是空格）。
if((y+1 >= Len || maze[y+1][x] != 0) && (y-1 < 0 || maze[y-1][x] != 0))
