文章目录
引入
实现功能：
1）setStart()：设置起点；
2）setEnd()：设置终点；
3）setWall()：设置墙壁；
4）findWay()：寻找路径；
5）display()：展示地图。
说明：
1）使用二维数组表示地图，边界默认为墙壁，无法更改，用1表示；
2）9表示起点，6表示终点；
3）2表示路径；
4）3表示不通；
5）找寻顺序为↓→↑←
初始地图示例如下：
1 0 0 0 0 0 0 1
1 9 0 0 0 0 0 1
1 1 1 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 0 0 0 0 1
1 0 0 1 0 6 0 1
1 1 1 1 1 1 1 1
路径找寻示例如下：
1 1 1 1 1 1 1 1
1 0 0 0 0 0 0 1
1 9 2 2 0 0 0 1
1 1 1 2 0 0 0 1
1 0 0 2 0 0 0 1
1 0 0 2 2 0 0 1
1 0 0 1 2 6 0 1
1 1 1 1 1 1 1 1
代码
package Test;
import java.util.Arrays;
import java.util.InputMismatchException;
/**
* @author: Inki
* @email: inki.yinji@qq.com
* @create: 2020 1111
* @last_modify: 2020 1112
*/
public class MazeBacktracking {
/**
* The default number rows.
*/
private final int NUMBER_ROW = 8;
/**
* The default number columns.
*/
private int NUMBER_COLUMN = 8;
/**
* Number rows.
*/
private int numRow;
/**
* Number columns.
*/
private int numColumn;
/**
* The maze matrix.
*/
private int[][] maze;
/**
* The start point index.
*/
private int[] start;
/**
* The end point index.
*/
private int[] end;
/**
* The first constructor.
*/
public MazeBacktracking() {
initialize(NUMBER_ROW, NUMBER_COLUMN);
}//Of first constructor
/**
* The first constructor.
*/
public MazeBacktracking(int paraNumRow, int paraNumColumn) {
initialize(paraNumRow, paraNumColumn);
}//Of first constructor
/**
* Initialize.
*
* @param: paraNumRow: The number of rows.
* paraNumColumn: The number of columns.
*/
private void initialize(int paraNumRow, int paraNumColumn) {
numRow = paraNumRow;
numColumn = paraNumColumn;
maze = new int[numRow][numColumn];
// Initialize walls.
Arrays.fill(maze[0], 1);
Arrays.fill(maze[numColumn - 1], 1);
for (int i = 1; i < numRow - 1; i++) {
maze[i][0] = maze[i][numColumn - 1] = 1;
}//Of for i
// Set start point.
start = new int[2];
start[0] = 1;
start[1] = 1;
// Set end point.
end = new int[2];
end[0] = numRow - 2;
end[1] = numColumn - 2;
}//Of initialize
/**
* Set start point.
*
* @param: paraStart:
* The start point index.
*/
public void setStart(int[] paraStart) {
if (paraStart.length != 2) {
throw new InputMismatchException("The columns of paraSite must equal 2.");
}//Of if
start = paraStart;
}//Of start
/**
* Set end point.
*
* @param: paraStart:
* The end point index.
*/
public void setEnd(int[] paraEnd) {
if (paraEnd.length != 2) {
throw new InputMismatchException("The columns of paraSite must equal 2.");
}//Of if
end = paraEnd;
}//Of start
/**
* Set wall.
*
* @param: paraSite:
* The site index of wall.
*/
public void setWall(int[] paraSite) {
int[][] tempSite = new int[1][];
tempSite[0] = paraSite;
setWall(tempSite);
}//Of setWall
/**
* Set walls.
*
* @param: paraSite:
* The site index of walls.
*/
public void setWall(int[][] paraSite) {
if (paraSite[0].length != 2) {
throw new InputMismatchException("The columns of paraSite must equal 2.");
}//Of if
for (int[] idx : paraSite) {
maze[idx[0]][idx[1]] = 1;
}//Of for i
}//Of setWall
/**
* Find ways.
*/
public boolean findWay() {
return findWay(start[0], start[0]);
}//Of findWay
/**
* Find ways.
*
* @param: paraI: The current index of row.
* paraJ: The current index of column.
*/
public boolean findWay(int pareI, int paraJ) {
if (maze[end[0]][end[1]] == 2) {
return true;
} else {
if (maze[pareI][paraJ] == 0) {
// Down --> right --> up --> left.
maze[pareI][paraJ] = 2;
if (findWay(pareI + 1, paraJ)) {
return true;
} else if (findWay(pareI, paraJ + 1)) {
return true;
} else if (findWay(pareI - 1, paraJ)) {
return true;
} else if (findWay(pareI, paraJ - 1)) {
return true;
} else {
maze[pareI][paraJ] = 3;
return false;
}//Of if
} else {
return false;
}//Of if
}//Of if
}//Of findWay
/**
* Display maze.
*/
public void display() {
for (int i = 0; i < numRow; i++) {
for (int j = 0; j < numColumn; j++) {
if (i == start[0] && j == start[1]) {
System.out.print("9 ");
} else if (i == end[0] && j == end[1]) {
System.out.print("6 ");
} else {
System.out.print(maze[i][j] + " ");
}//Of if
}//of for j
System.out.println();
}//Of for i
System.out.println();
}//Of display
/**
* The main.
*/
public static void main(String[] args) {
MazeBacktracking test = new MazeBacktracking();
int[][] tempSite = {
{
3, 1}, {
3, 2}, {
6, 3}};
int[] tempStart = {
2, 1};
int[] tempEnd = {
6, 5};
test.setStart(tempStart);
test.setEnd(tempEnd);
test.setWall(tempSite);
test.display();
test.findWay();
test.display();
}//Of main
}//Of class MazeBacktracking
本文分享 CSDN - 因吉。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
