用一個7 x 7的矩形表示迷宮，0和1分別表示的是通路和障礙。通過設計編寫程序找到藍色小球達到藍色旗子的路線
思路：
構建一個迷宮（用二維數組）實現找通路的方法findRoad()
構建二維數組不難，我們主要是要實現findRoad()這個方法，在實現這個方法前，我們需要約定好一下幾個點：小球的位置當作入口（1，1），小旗的位置當作出口（5，5）數組里數的含義分別為(0沒有走過)、(1障礙)、(2走過且為正確的路線)、(3走過且為錯誤的路線)將我們每一步的走法稱為策略：下 -> 右 -> 上 ->左
實現
首先構建出迷宮
java" id="highlighter_632885">
|
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
|
public static void main(String[] args) { //1.創建二維數組模擬迷宮 int[][] maze = new int[7][7]; //2.初始化迷宮 for (int i = 0; i < maze.length; i++) { //maze[i][j]:i控制行 j:控制列 maze[0][i] = 1;//第1行都為1 maze[6][i] = 1;//最后一行都為1 maze[i][0] = 1;//第一列都為1 maze[i][6] = 1;//最后一列都為1 //其他位置的1 maze[4][1] = 1; maze[4][2] = 1; maze[4][3] = 1; maze[4][4] = 1; maze[3][4] = 1; maze[2][3] = 1; } //打印迷宮 System.out.println("完成迷宮初始化："); for (int i = 0; i < maze.length; i++) { for (int j = 0; j < maze[i].length; j++) { System.out.print(maze[i][j] + " "); } System.out.println(); } } |
然后寫findRoad()方法
|
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
|
* 使用遞歸回溯找通路 （5，5為出口） * @param maze 迷宮 * @param i 從哪個位置開始找 * @param j 從哪個位置開始找 * @return 找到通路返回true 否則false */public static boolean findRoad(int[][] maze, int i, int j) { //策略：下 -> 右 -> 上 ->左 //0：沒有走過 1：障礙 2:走過且為正確的路線 3：走過且為錯誤的路線 if (maze[5][5] == 2) {//找到通路 return true; } else { if (maze[i][j] == 0) { //當前點沒走過，按策略走 maze[i][j] = 2;//當前點改為2，假定能走通 if (findRoad(maze, i + 1, j)) {//向下走 return true; } else if (findRoad(maze, i, j + 1)) {//向右走 return true; } else if (findRoad(maze, i - 1, j)) {//向上走 return true; } else if (findRoad(maze, i, j - 1)) {//向左走 return true; } else { //該點無法走通 maze[i][j] = 3; return false;//返回到上個方法（即返回到上個點） } } else { //該點為 1或2或3，無法走通，直接返回上個方法（即上個點） return false; } }} |
main方法調用findRoad()方法，傳入創建好的迷宮，和入口點（1，1）
|
1
2
3
4
5
6
7
8
9
10
|
//mian方法中調用findRoad()方法 findRoad(maze,1,1); //打印迷宮 System.out.println("完成路線的迷宮："); for (int i = 0; i < maze.length; i++) { for (int j = 0; j < maze[i].length; j++) { System.out.print(maze[i][j] + " "); } System.out.println(); } |
效果
到此這篇關于java 實現迷宮回溯算法示例詳解的文章就介紹到這了,更多相關java 實現迷宮回溯算法內容請搜索服務器之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持服務器之家！
原文鏈接：https://blog.csdn.net/weixin_47254987/article/details/107666338
