DFS & BFS

三维迷宫——地牢大师

题目描述：2251 – 地下城主

import java.util.*;

class PIIs {
    public int x;//第x层
    public int y;//第y行
    public int z;//第z列
    public int dist;
    public PIIs(int x,int y,int z, int dist) {
        this.x = x;
        this.y = y;
        this.z = z;
        this.dist = dist;
    }
}


public class Main {
    static PIIs start;
    static PIIs end;
    static int L, R, C;
    static int N = 100;
    static char[][][] g = new char[N][N][N];
    static final int[] dx = {-1, 1, 0, 0, 0, 0};
    static final int[] dy = {0, 0, -1, 1, 0, 0};
    static final int[] dz = {0, 0, 0, 0, -1, 1};
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        while(scan.hasNext()) {
            L = scan.nextInt();
            R = scan.nextInt();
            C = scan.nextInt();
            if(L == 0 && R == 0 && C == 0) break;
            for(int i = 0;i < L; i ++) {
                for(int j = 0;j < R; j++) {
                    char[] charArray = scan.next().toCharArray();
                    for(int k = 0; k < C; k++) {
                        g[i][j][k] = charArray[k];
                        if(g[i][j][k] == 'S') start = new PIIs(i, j, k, 0);
                        if(g[i][j][k] == 'E') end = new PIIs(i, j, k, 0);
                    }
                }
            }
            int distance = bfs();
            if(distance == -1) System.out.println("Trapped!");
            else System.out.println("Escaped in " + distance + " minute(s).");
        }
    }

    public static int bfs() {
        Queue<PIIs> quene = new LinkedList<PIIs>();
        quene.add(start);
        while (!quene.isEmpty()) {
            PIIs piIs = quene.poll();
            if (piIs.x == end.x && piIs.y == end.y && piIs.z == end.z) return piIs.dist;
            for (int i = 0; i < 6; i++) {
                int x = piIs.x + dx[i];
                int y = piIs.y + dy[i];
                int z = piIs.z + dz[i];
                if (x < 0 || x >= L || y < 0 || y >= R || z < 0 || z >= C || g[x][y][z] == '#') {
                    continue;
                }
                g[x][y][z] = '#';
                quene.offer(new PIIs(x, y, z, piIs.dist + 1));
            }
        }
        return -1;
    }
}

图的DFS

import java.util.*;

class DepthFirstSearch {
    private Map<Integer, List<Integer>> graph;
    private boolean[] visited;

    public DepthFirstSearch(Map<Integer, List<Integer>> graph) {
        this.graph = graph;
        this.visited = new boolean[graph.size()];
    }

    public void dfs(int start) {
        Stack<Integer> stack = new Stack<>();
        stack.push(start);
        visited[start] = true;

        while (!stack.isEmpty()) {
            int node = stack.pop();
            System.out.print(node + " ");

            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    stack.push(neighbor);
                }
            }
        }
    }
}


public class Main {
    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(3));
        graph.put(2, Arrays.asList(3));
        graph.put(3, Collections.emptyList());

        DepthFirstSearch dfs = new DepthFirstSearch(graph);
        dfs.dfs(0); // 应输出 0 2 3 1
    }
}

图的BFS

import java.util.*;

class BreadthFirstSearch {
    private Map<Integer, List<Integer>> graph;
    private boolean[] visited;

    public BreadthFirstSearch(Map<Integer, List<Integer>> graph) {
        this.graph = graph;
        this.visited = new boolean[graph.size()];
    }

    public void bfs(int start) {
        Queue<Integer> quene = new LinkedList<>();
        quene.offer(start);
        visited[start] = true;

        while (!quene.isEmpty()) {
            int node = quene.poll();
            System.out.print(node + " ");

            for (int neighbor : graph.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    quene.offer(neighbor);
                }
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        graph.put(0, Arrays.asList(1, 2));
        graph.put(1, Arrays.asList(3));
        graph.put(2, Arrays.asList(3));
        graph.put(3, Collections.emptyList());

        BreadthFirstSearch bfs = new BreadthFirstSearch(graph);
        bfs.bfs(0); // 应输出 0 1 2 3
    }
}