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();
        }
    }
}