迷宫问题_走迷宫

迷宫问题

迷宫问题

import java.util.*;
class pair{
    //保存坐标!
    public int x;
    public int y;
    public pair(int x,int y){
        this.x = x;
        this.y = y;
    }
}
public class Main{
    static int[][] next = {{-1,0},{1,0},{0,-1},{0,1}};
    public static boolean DFS(int[][] array,int row,int col,int curx,int cury,ArrayList<pair> result){
        if(curx==row-1&&cury==col-1){
            return true;//结束! 已经找到了该路径!
        }
        for(int i = 0;i<next.length;i++){
            int x = curx + next[i][0];
            int y = cury + next[i][1];
            if(x<0||x>=row||y<0||y>=col){
                //越界
                continue;
            }
            if(array[x][y]==0){
                //可走!
                //保存该位置!
                result.add(new pair(x,y));
                //标记该位置走过!
                array[x][y] = 1;
                if(DFS(array,row,col,x,y,result)){
                    //到达了
                    return true;
                }
                //回溯
                result.remove(result.size()-1);
                array[x][y] = 0;
            }
        }
        //未找到该路径需要回退!
        return false;
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            int row = sc.nextInt();
            int col = sc.nextInt();
            int[][] array = new int[row][col];
            for(int i = 0;i<row;i++){
                for(int j = 0;j<col;j++){
                    array[i][j] = sc.nextInt();
                }
            }
            ArrayList<pair> result = new ArrayList<>();
            result.add(new pair(0,0));
            DFS(array,row,col,0,0,result);
            for(pair cur:result){
                System.out.println("("+cur.x+","+cur.y+")");
            }
        }
    }
}

走迷宫

走迷宫

// dfs深度优先搜索
import java.util.*;
public class Main{
    static int[][] direction = {{0,-1}, {-1,0}, {0,1}, {1,0}};
    public static void dfs(int x, int y, char[][] maze, int[][] map){
        for(int i = 0; i < 4; i++){
            int xx = x + direction[i][0];
            int yy = y + direction[i][1];
            if(xx >= 0 && xx < 10 && yy >= 0 && yy < 10 
              && maze[xx][yy] == '.' && map[xx][yy] > map[x][y]+1){
                map[xx][yy] = map[x][y] + 1;
                dfs(xx, yy, maze, map);
            }
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            char[][] maze = new char[10][10];
            int[][] map = new int[10][10];
            for(int i = 0; i < 10; i++){
                String str = sc.next();
                for(int j = 0; j < 10; j++){
                    maze[i][j] = str.charAt(j);
                    map[i][j] = Integer.MAX_VALUE;
                }
            }
            map[0][1] = 0;
            dfs(0, 1, maze, map);
            System.out.println(map[9][8]);
        }
    }
}

// bfs广度优先搜索
import java.util.*;
public class Main{
    static int[][] direction = {{0,-1}, {-1,0}, {0,1}, {1,0}};
    static class Node{
        int x, y;
        public Node(int x, int y){
            this.x = x;
            this.y = y;
        }
    }
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            char[][] maze = new char[10][10];
            int[][] map = new int[10][10];
            boolean[][] visited = new boolean[10][10];
            for(int i = 0; i < 10; i++){
                String str = sc.next();
                for(int j = 0; j < 10; j++){
                    maze[i][j] = str.charAt(j);
                    if(maze[i][j] == '#'){
                        visited[i][j] = true;
                    }
                }
            }
            Queue<Node> queue = new LinkedList<>();
            queue.offer(new Node(0, 1));
            while(!queue.isEmpty()){
                Node cur = queue.poll();
                for(int i = 0; i < 4; i++){
                    Node next = new Node(cur.x+direction[i][0], cur.y+direction[i][1]);
                    if(next.x >= 0 && next.x < 10 && next.y >= 0 && next.y < 10 
                      && !visited[next.x][next.y]){
                        queue.offer(next);
                        map[next.x][next.y] = map[cur.x][cur.y] + 1;
                        visited[next.x][next.y] = true;
                    }
                }
            }
            System.out.println(map[9][8]);
        }
    }
}

//bfs2
// write your code here
import java.util.*;
class pare {
    int x;
    int y;
    int step;
    public pare(int x,int y,int step){
        this.x = x;
        this.y = y;
        this.step = step;
    }
}
public class Main{
    public static int[][] next = {{0,1},{0,-1},{1,0},{-1,0}};
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        char[][] map = new char[10][10];
        while(sc.hasNext()){
            for(int i = 0;i<10;i++){
                String tmp = sc.nextLine();
                for(int j = 0;j<10;j++){
                    map[i][j] = tmp.charAt(j);
                }
            }
            pare start = new pare(0,1,0);
            System.out.println(bfs(map,10,10,start));
        }
    }
    public static int bfs(char[][] map,int row,int col,pare start){
        //广度优先!
        Queue<pare> q = new LinkedList<>();
        q.offer(start);
        while (!q.isEmpty()){
            pare cur = q.poll();
            if(cur.x==9&&cur.y==8){
                return cur.step;
            }
            for (int i = 0; i <next.length; i++) {
                int x = cur.x + next[i][0];
                int y = cur.y + next[i][1];
                int step = cur.step + 1;
                if(x>=0&&x<row&&y>=0&&y<col&&map[x][y]=='.'){
                    //标记已经走过!
                    map[x][y] = '#';
                    //入队!
                    q.offer(new pare(x,y,step));
                }
            }
        }
        return 0;
    }
}