- 问题
- 问题分析
- 代码实现
- 结束语
在一个地图上，给你一个起点、一个终点、地图上有障碍物，让你制定一条走到终点的路线（不需要求最短路径）
如图：
“1”表示障碍物 ， “0”表示可走的路， （1,1)是起点，（6,5）是终点
（外围的障碍物不算坐标，且数组下标从0开始）
问题分析
解决这个问题就是求出从入口到出口的路径，在求解时，通常用的是“穷举求解”的方法，即从入口出发，顺着某一个方向向前试探，若能走通，则继续往前走，否则沿着原路退回（回溯），换一个方向再继续试探，直到到达终点为止。
有点类似于 深度优先搜索（深度优先搜索求的是最短路径，也就是最优解，深度优先这个算法后续我会再总结）。
认真思考我们会发现，其实找路的方式都是一样的
- 首先看当前位置是否可走？如果不可走就原路返回、往回走
- 如果当前位置可走，则再走下一步，看当前位置的上、下、左、右的路是否可走（当然究竟是先走上？先走下？先走左？先走右？ 这个选择的顺序是自己定的，这个决策会影响到你最终找的路线）
这样一来，其实我们已经将从起点到终点这个大问题 拆分为了一个个从当前位置找下一步的小问题。
代码实现
编码约定
- 地图我用一个二维数组表示
- 数字“1”表示墙，数字“0”表示路
- （1,1）位置表示起点，（6,5）位置表示终点
- 数字“2”的标记表示该点已走过，数字“3”的标记表示该点是死路、前面走不通
- 终点（6,5）的值默认为0，如果走到该点了就将其赋值为数字“6”（听起来比较吉利）
上代码
public static void main(String[] args) {
//先创建一个二维数组，用于模拟迷宫
int[][] map = new int[8][7];
//使用1表示墙，上下全部为1
for (int i = 0; i < 7; i++) {
map[0][i] = 1;
map[7][i] = 1;
}
//左右全部为1
for (int i = 0; i < 8; i++) {
map[i][0] = 1;
map[i][6] = 1;
}
map[6][1] = 1;
map[3][2] = 1;
map[5][2] = 1;
map[4][2] = 1;
map[2][3] = 1;
// map[1][3] = 1;
//打印输出迷宫，也就是打印输出二维数组
System.out.println("地图的情况：");
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j] + "t");
}
System.out.println();
}
System.out.println("=========================================");
//调用自定义的setWay方法找路
setWay(map, 1, 1);
System.out.println("探测过的地图：");
for (int i = 0; i < 8; i++) {
for (int j = 0; j < 7; j++) {
System.out.print(map[i][j] + "t");
}
System.out.println();
}
}
public static void setWay(int[][] map,int i,int j){
if (i==6 && j==5)
{
//已经到达终点
System.out.println("已经到达终点");
map[i][j] = 6;
return; // 回溯
}
else
{
if (map[i][j] == 0){ // 如果当前位置为0，则表示当前位置可走。然后再按照策略走下一步，下右上左的方向走
// 将当前位置赋值为2 标记该位置已走
map[i][j] = 2;
// 开始寻找走下一步
if (map[i+1][j] == 0){ //表示向下走
System.out.println("向↓走");
setWay(map, i+1, j);
// 如果从setWay这个子栈帧 返回回来 有两种情况 1、前面的路已经走不通（不可走）才返回的 2、已经找到迷宫终点才返回的
System.out.println("从"+(i+1)+"行"+j+"列回溯回来了， ↑");
// 如果是因为终点找到才返回的 那么此刻我们需要继续回溯，直接return ； 否则我们就不return，而是选择走其他方向的路
if (map[6][5] == 6) return;
}
if (map[i][j+1] == 0){ //表示向右走
System.out.println("向→走");
setWay(map, i, j+1);
System.out.println("从"+i+"行"+(j+1)+"列回溯回来了， ←");
if (map[6][5] == 6) return;
}
if (map[i-1][j] == 0){ //表示向上走
System.out.println("向↑走");
setWay(map, i-1, j);
System.out.println("从"+(i-1)+"行"+j+"列回溯回来了， ↓");
if (map[6][5] == 6) return;
}
if (map[i][j-1] == 0){ //表示向左走
System.out.println("向←走");
setWay(map, i, j-1);
System.out.println("从"+i+"行"+(j-1)+"列回溯回来了， →");
if (map[6][5] == 6) return;
}
//按照下右上左的顺序走完都走不通，则标记当前点为3，是死路
map[i][j] = 3;
System.out.println("走不通"+i+"行"+j+"列");
return; // 回溯
}
else {
//当前点如果不为0，还可能为1、或者2、或者3 都表示不可走
return; // 回溯
}
}
}
简约版的setWay方法(还是上面的逻辑)
public static void setWay1(int[][] map, int row, int col) {
if (row==6 && col==5) { // 如果到达（6,5）也就说明 已经到达了终点 直接回溯
map[row][col] = 6; // 将其赋值为6 （这个6 只是一个特殊值 没有啥特殊含义）
return;
}else {
if (map[row][col] == 0) { // 如果该点为0 则表示可以走
// 1、首先将该点 置为2 以此来表示该点已走过
map[row][col] = 2;
// 2、按计划找下一步 先往↓ 再往→ 后往↑ 最后往← 的顺序 走下一步
if (map[row+1][col] == 0) { // 如果向 ↓ 可走
setWay1(map, row+1, col); // 往这个方向往后走
if (map[6][5] == 6) return;
}
if (map[row][col+1] == 0) { // 如果向 → 可走
setWay1(map, row, col+1); // 往这个方向往后走
if (map[6][5] == 6) return;
}
if (map[row-1][col] == 0) { // 如果向 ↑ 可走
setWay1(map, row-1, col); // 往这个方向往后走
if (map[6][5] == 6) return;
}
if (map[row][col-1] == 0) { // 如果向 ← 可走
setWay1(map, row, col-1); // 往这个方向往后走
if (map[6][5] == 6) return;
}
// 3、如果四个方向都走不通 则表示该点是死路 将其赋值为 3 然后return 回溯
map[row][col] = 3;
return;
}else { // 如果不为0 则表示该点不可走 可能是 2、 3、 6 直接return 回溯
return;
}
}
}
结束语
算法这东西，不光要多看、多想，最主要的是多练，自己手敲一遍才更有效。
如果这篇文章有帮助到你，点击赞呗(*^▽^*)！
