• 【算法 | 实验6-1】n*n的网格，从左上角开始到右下角结束遍历所有的方块仅一次，总共有多少种不同的遍历路径

    文章目录

    前言

    思路介绍中省略了关于如何进行回溯搜索的细节，而主要讨论回溯中所使用的剪枝策略。

    题

    在这里插入图片描述
    对于如图7×7的网格，从左上角开始到右下角结束遍历所有的方块仅一次，总共有多少种不同的遍历路径？

    思路

    基本思路：回溯法进行搜索。但纯暴力的搜索时间复杂度太大，需要加上剪枝的优化。
    剪枝：可剪掉会导致不连通的走法，每走一步都判断是否联通。例如下图中的第五步，就将网格划分成了两片不连通的区域。

    在这里插入图片描述

    判断联通性，思路1：

    for 格子 in 所有网格
	if(以该格子作为起点进行搜索，能找到一条到达终点的路径)
		该格子与终点联通
		
if(所有格子都与终点联通)
	所有网格之间是联通的

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    即在一次是否联通的判断中，对应每个空的（没走过的）格子都进行一次回溯搜索。
    到这里可能就会疑惑，剪枝的代价这么大，值得吗？答案是值得的，可以自己写有剪枝和纯暴力的程序对比一下。
    看似一下只剪掉了一种情况，有时其实剪掉的相连的枝条是非常多的。
    在这里插入图片描述
    剪枝效果：对题中 7 * 7 的网格，程序需要运行 2~3 分钟才能得到结果（毕竟搜索的基数还是太大了）。然而比纯暴力的情况好很多（纯暴力搜索我根本没看到结果）。

    判断联通性，思路2：

    前面的剪枝虽然有一些效果（至少可以看得见结果），然而每次剪枝代价还是偏大。每次判断联通，都对每个格子应用一次回溯搜索其实是不必要的。
    那是一种比较静态的思路，你给我一张网格，告诉我哪些格子走过了（被覆盖），哪些格子没走过（空白），然后我告诉你它是不是联通。

    另一种想法，就是考虑怎样走会导致不连通，因为状态从联通到不连通的转变只在某一步。
    要把一块区域困死，走的路径就肯定会形成闭环，可以作以下断言：

    if(我某一步后，前方是墙壁或走过的格子，且此时我两边都是没走过的格子）
	不连通
else
	联通

    • 1
    • 2
    • 3
    • 4

    在这里插入图片描述
    对剪枝进行优化后，仅需 2~3 秒即得到结果。

    在这里插入图片描述

    实现（C++）

    思路1

    #include
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81
    • 82
    • 83
    • 84
    • 85
    • 86
    • 87
    • 88
    • 89
    • 90
    • 91
    • 92
    • 93
    • 94
    • 95
    • 96
    • 97
    • 98
    • 99
    • 100
    • 101
    • 102
    • 103
    • 104
    • 105
    • 106
    • 107
    • 108
    • 109
    • 110
    • 111
    • 112
    • 113
    • 114
    • 115
    • 116
    • 117
    • 118
    • 119
    • 120
    • 121
    • 122
    • 123
    • 124
    • 125
    • 126
    • 127
    • 128
    • 129
    • 130
    • 131
    • 132
    • 133
    • 134
    • 135
    • 136
    • 137
    • 138
    • 139
    • 140
    • 141
    • 142
    • 143
    • 144
    • 145
    • 146
    • 147
    • 148
    • 149
    • 150
    • 151
    • 152
    • 153
    • 154
    • 155
    • 156

    思路2

    //1.剪枝：不连通 
#include
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;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79
    • 80
    • 81

    bug记录

    在写live()函数时，我一开始的 if 语句如下。只有当前位置的上方或下方不是空格子，就判断为“碰到墙壁”。

    //向上碰壁或向下碰壁
if(y+1 >= Len || maze[y+1][x] != 0 || y-1 < 0 || maze[y-1][x] != 0)

    • 1
    • 2

    但后面发现，我给live()这个函数并没有传递“这一步是向哪个方向走达到的”这个方向信息，要判断碰壁应改为下面的代码（碰壁时，来的方向和走向的方向肯定都不是空格）。

    if((y+1 >= Len || maze[y+1][x] != 0) && (y-1 < 0 || maze[y-1][x] != 0))

    • 1

    14天阅读挑战赛

  • 相关阅读:
    教你使用华为云函数进行签名校验
    尚好房 11_Session共享
    [附源码]Python计算机毕业设计Django教务管理系统
    如何解决PHP base64编码后解码乱码的问题
    解决 Could not resolve com.android.tools.build:gradle:4.2.2 问题
    OSI参考模型
    基础 IO (Linux学习笔记)
    计算机网络_2.2物理层下面的传输媒体
    2022年最新青海机动车签字授权人模拟考试及答案
    JVM面试速补：知识点梳理+学习路线+学习笔记+真题解析，够不够？
  • 原文地址：https://blog.csdn.net/m0_63238256/article/details/127379122