DFS 迷宫
从指定起点开始,绕过病毒,选择最优路径到达终点。
Python:
# coding:utf-8
class Maze:
path = ""
shortest_path = ""
def dfs_maze(self, x, y, maze):
m = len(maze)
n = len(maze[0])
# 结束条件
if x < 0 or y < 0:
return
# 越界 or 遇到病毒
if x > m - 1 or y > n - 1 or maze[x][y] == 1:
return
# 终点
if maze[x][y] == 9:
self.path = self.path + str(x) + "," + str(y)
if len(self.shortest_path) == 0 or len(self.shortest_path) > len(self.path):
self.shortest_path = self.path
print("shortest-path: ", self.shortest_path)
return
t = self.path
# 记录路线
self.path = self.path + str(x) + "," + str(y) + "-"
# 标记走过的路线
maze[x][y] = 1
# 向4个方向搜索
self.dfs_maze(x + 1, y, maze)
self.dfs_maze(x, y + 1, maze)
self.dfs_maze(x, y - 1, maze)
self.dfs_maze(x - 1, y, maze)
maze[x][y] = 0
self.path = t
def print_maze(self, maze, shortest_self):
# 用-分割字符串,得到 x,y
p = shortest_self.split('-')
# 循环将路径的值改成8,表示“西南”
for xy in p[0:-1]:
x = int(xy[0])
y = int(xy[2])
maze[x][y] = 8
for i in maze:
line = ""
for j in i:
if j == 0:
line = line + '**\t'
if j == 1:
line = line + '病毒\t'
if j == 9:
line += '终点\t'
if j == 8:
line += 'XX\t'
print(line)
if __name__ == '__main__':
maze = [[0, 1, 0, 1, 0, 0, 0],
[1, 1, 0, 1, 0, 1, 0],
[0, 0, 0, 0, 0, 0, 0],
[0, 0, 1, 0, 1, 0, 1],
[0, 1, 0, 9, 1, 0, 1],
[0, 0, 0, 1, 0, 0, 0],
[0, 1, 0, 0, 0, 1, 0],
[1, 0, 0, 1, 0, 0, 0],
[1, 0, 0, 0, 0, 1, 0]]
m = Maze()
m.dfs_maze(8, 3, maze)
m.print_maze(maze, m.shortest_path)
Java:
public class Maze{
private static String path = "";
private static String sp = "";
public static void main(String[] args){
int[][] maze = new int[][]{
{0,1,0,1,0,0,0},
{1,1,0,1,0,1,0},
{0,0,0,0,0,0,0},
{0,0,1,0,1,0,1},
{0,1,0,'T',1,0,1},
{0,0,0,1,0,0,0},
{0,1,0,0,0,1,0},
{1,0,0,1,0,0,0},
{1,0,0,0,0,1,0}
};
dfsMaze(8, 3, maze);
printMaze(maze, sp);
}
public static void dfsMaze(int x, int y, int[][] maze){
int m = maze.length;
int n = maze[0].length;
if(x < 0 || y < 0 ) return;
if(x > m-1 || y > n-1 || maze[x][y] == 1) return;
if(maze[x][y] == 'T'){
path = path + x + "," + y ;
if(sp.length()==0 || sp.length() > path.length()){
sp = path;
}
return;
}
String t = path;
path = path + x + "," + y + "-";
maze[x][y] = 1;
dfsMaze(x, y+1, maze);
dfsMaze(x, y-1, maze);
dfsMaze(x+1, y, maze);
dfsMaze(x-1, y, maze);
maze[x][y] = 0;
path = t;
}
public static void printMaze(int[][] maze, String path){
System.out.println(path);
String[] pathArr = path.split("-");
for(int i=0; i<pathArr.length-1; i++){
String[] p = pathArr[i].split(",");
maze[Integer.parseInt(p[0])][Integer.parseInt(p[1])] = 'P';
}
for(int ii=0; ii<maze.length; ii++){
for(int jj=0; jj<maze[ii].length; jj++){
if(maze[ii][jj] == 0){
System.out.print("--\t");
}
if (maze[ii][jj] == 1){
System.out.print("病毒\t");
}
if(maze[ii][jj] == 'T'){
System.out.print("终点\t");
}
if(maze[ii][jj] == 'P'){
System.out.print("西南\t");
}
}
System.out.println();
}
}
}