文章目录
引入
实现功能：
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
代码
1package Test; 2 3import java.util.Arrays; 4import java.util.InputMismatchException; 5 6/** 7 * @author: Inki 8 * @email: inki.yinji@qq.com 9 * @create: 2020 1111 10 * @last_modify: 2020 1112 11 */ 12public class MazeBacktracking { 13 14 15 16 17 /** 18 * The default number rows. 19 */ 20 private final int NUMBER_ROW = 8; 21 22 /** 23 * The default number columns. 24 */ 25 private int NUMBER_COLUMN = 8; 26 27 /** 28 * Number rows. 29 */ 30 private int numRow; 31 32 /** 33 * Number columns. 34 */ 35 private int numColumn; 36 37 /** 38 * The maze matrix. 39 */ 40 private int[][] maze; 41 42 /** 43 * The start point index. 44 */ 45 private int[] start; 46 47 /** 48 * The end point index. 49 */ 50 private int[] end; 51 52 /** 53 * The first constructor. 54 */ 55 public MazeBacktracking() { 56 57 58 59 initialize(NUMBER_ROW, NUMBER_COLUMN); 60 }//Of first constructor 61 62 /** 63 * The first constructor. 64 */ 65 public MazeBacktracking(int paraNumRow, int paraNumColumn) { 66 67 68 69 initialize(paraNumRow, paraNumColumn); 70 }//Of first constructor 71 72 /** 73 * Initialize. 74 * 75 * @param: paraNumRow: The number of rows. 76 * paraNumColumn: The number of columns. 77 */ 78 private void initialize(int paraNumRow, int paraNumColumn) { 79 80 81 82 numRow = paraNumRow; 83 numColumn = paraNumColumn; 84 maze = new int[numRow][numColumn]; 85 86 // Initialize walls. 87 Arrays.fill(maze[0], 1); 88 Arrays.fill(maze[numColumn - 1], 1); 89 for (int i = 1; i < numRow - 1; i++) { 90 91 92 93 maze[i][0] = maze[i][numColumn - 1] = 1; 94 }//Of for i 95 96 // Set start point. 97 start = new int[2]; 98 start[0] = 1; 99 start[1] = 1; 100 101 // Set end point. 102 end = new int[2]; 103 end[0] = numRow - 2; 104 end[1] = numColumn - 2; 105 }//Of initialize 106 107 /** 108 * Set start point. 109 * 110 * @param: paraStart: 111 * The start point index. 112 */ 113 public void setStart(int[] paraStart) { 114 115 116 117 118 if (paraStart.length != 2) { 119 120 121 122 throw new InputMismatchException("The columns of paraSite must equal 2."); 123 }//Of if 124 125 start = paraStart; 126 127 }//Of start 128 129 /** 130 * Set end point. 131 * 132 * @param: paraStart: 133 * The end point index. 134 */ 135 public void setEnd(int[] paraEnd) { 136 137 138 139 140 if (paraEnd.length != 2) { 141 142 143 144 throw new InputMismatchException("The columns of paraSite must equal 2."); 145 }//Of if 146 147 end = paraEnd; 148 149 }//Of start 150 151 /** 152 * Set wall. 153 * 154 * @param: paraSite: 155 * The site index of wall. 156 */ 157 public void setWall(int[] paraSite) { 158 159 160 161 int[][] tempSite = new int[1][]; 162 tempSite[0] = paraSite; 163 setWall(tempSite); 164 }//Of setWall 165 166 /** 167 * Set walls. 168 * 169 * @param: paraSite: 170 * The site index of walls. 171 */ 172 public void setWall(int[][] paraSite) { 173 174 175 176 177 if (paraSite[0].length != 2) { 178 179 180 181 throw new InputMismatchException("The columns of paraSite must equal 2."); 182 }//Of if 183 184 for (int[] idx : paraSite) { 185 186 187 188 maze[idx[0]][idx[1]] = 1; 189 }//Of for i 190 191 }//Of setWall 192 193 /** 194 * Find ways. 195 */ 196 public boolean findWay() { 197 198 199 200 return findWay(start[0], start[0]); 201 }//Of findWay 202 203 /** 204 * Find ways. 205 * 206 * @param: paraI: The current index of row. 207 * paraJ: The current index of column. 208 */ 209 public boolean findWay(int pareI, int paraJ) { 210 211 212 213 if (maze[end[0]][end[1]] == 2) { 214 215 216 217 return true; 218 } else { 219 220 221 222 if (maze[pareI][paraJ] == 0) { 223 224 225 226 // Down --> right --> up --> left. 227 maze[pareI][paraJ] = 2; 228 if (findWay(pareI + 1, paraJ)) { 229 230 231 232 return true; 233 } else if (findWay(pareI, paraJ + 1)) { 234 235 236 237 return true; 238 } else if (findWay(pareI - 1, paraJ)) { 239 240 241 242 return true; 243 } else if (findWay(pareI, paraJ - 1)) { 244 245 246 247 return true; 248 } else { 249 250 251 252 maze[pareI][paraJ] = 3; 253 return false; 254 }//Of if 255 } else { 256 257 258 259 return false; 260 }//Of if 261 }//Of if 262 263 }//Of findWay 264 265 /** 266 * Display maze. 267 */ 268 public void display() { 269 270 271 272 273 for (int i = 0; i < numRow; i++) { 274 275 276 277 for (int j = 0; j < numColumn; j++) { 278 279 280 281 if (i == start[0] && j == start[1]) { 282 283 284 285 System.out.print("9 "); 286 } else if (i == end[0] && j == end[1]) { 287 288 289 290 System.out.print("6 "); 291 } else { 292 293 294 295 System.out.print(maze[i][j] + " "); 296 }//Of if 297 }//of for j 298 System.out.println(); 299 }//Of for i 300 System.out.println(); 301 302 }//Of display 303 304 /** 305 * The main. 306 */ 307 public static void main(String[] args) { 308 309 310 311 MazeBacktracking test = new MazeBacktracking(); 312 int[][] tempSite = { 313 314 315 { 316 317 318 3, 1}, { 319 320 321 3, 2}, { 322 323 324 6, 3}}; 325 int[] tempStart = { 326 327 328 2, 1}; 329 int[] tempEnd = { 330 331 332 6, 5}; 333 test.setStart(tempStart); 334 test.setEnd(tempEnd); 335 test.setWall(tempSite); 336 test.display(); 337 test.findWay(); 338 test.display(); 339 }//Of main 340 341}//Of class MazeBacktracking
本文分享 CSDN - 因吉。
如有侵权，请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。