当前位置: 代码迷 >> 综合 >> JAVA算法:走迷宫回溯算法设计(JAVA版本)
  详细解决方案

JAVA算法:走迷宫回溯算法设计(JAVA版本)

热度:23   发布时间:2024-01-15 19:23:45.0

JAVA算法:走迷宫回溯算法设计(JAVA版本)

迷宫数组

     int[][] maze = {
                {0, 1, 0, 0, 0},
                {0, 1, 0, 1, 0},
                {0, 0, 0, 0, 0},
                {0, 1, 1, 1, 0},
                {0, 0, 0, 1, 0}
        };

 

算法思路

将迷宫问题对应为二维数组,数组中只有两种值0和1,其中0,1分别表示通路和墙。

不过在解决这个问题的时候一般要在最外面添加一个围墙,这里设置每个围墙都为1,这样有利于防止当走到了迷宫的出口处还会向前走,这个并不一定,只是最一般的方法,也是最有利于理解的方法。

这里的利用到了回溯法,需要走到了一个位置,然后向四处试探,如果有一个方向可以走了就将当前的点压入栈,并且标记当前点以便于区分是否走过,如果四处都无出路,只需要回到前一个走到的点,然后从前一个点再换一个方向重新走。

算法设计

设计一个Position类,用来表示迷宫中位置点(坐标)

package com.bean.algorithm.maze;public class Position {public int row;public int col;public Position(int row, int col) {