POJ 刷题系列：3026. Borg Maze

传送门：3026. Borg Maze

题意：

给出一张迷宫图，墙用”#”表示，起始点为”S”, 外星人为”A”，求从S出发，连通”A”的最短路径。注意：”A”和”A”之间相连也算连通。

思路：

BFS PRIME，算比较综合了，BFS为了求每个”A”之间的最短距离，接着PRIME求MST即可。需要注意，地图中并非所有顶点有有效距离，所以把除A和S之外的顶点都当访问过，这样可以避免求出这些无效顶点的距离。

代码如下：

代码语言：javascript复制

import java.io.IOException;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main{

    static Scanner in;
    public static void main(String[] args) throws IOException {
        in = new Scanner(System.in);
        new Main().run();
    }

    static final int INF = 0x3f3f3f3f;

    char[][] map;
    int[][] dist;

    void run() {
        int T = in.nextInt();
        while (T --> 0) {
            String s = in.nextLine();
            while (s.isEmpty()) s = in.nextLine();
            String[] ss = s.split(" ");
            int x = Integer.parseInt(ss[0]);
            int y = Integer.parseInt(ss[1]);
            map = new char[y][x];
            int i = 0;
            while(true) {
                if (i == y) break;
                String ns = in.nextLine();
                if (ns.isEmpty()) continue;
                if (i == 0 || i == y - 1) {
                    for (int j = 0; j < x;   j) {
                        map[i][j] = '#';
                    }
                }
                else {
                    for (int j = 0; j < x;   j) {
                        map[i][j] = ns.charAt(j);
                    }
                }
                i   ;
            }
            int V = x * y;
            dist = new int[V][V];
            for (int j = 0; j < V;   j) Arrays.fill(dist[j], INF);

            int S = -1;
            Set<Integer> isV = new HashSet<Integer>();
            for (i = 0; i < y;   i) {
                for (int j = 0; j < x;   j) {
                    if (map[i][j] == 'S') {
                        S = i * x   j;
                        isV.add(S);
                        bfs(S, y, x);
                    }
                    else if (map[i][j] == 'A'){
                        bfs(i * x   j, y, x);
                        isV.add(i * x   j);
                    }
                }
            }

            // prime
            int[] mincost = new int[V];
            Arrays.fill(mincost, INF);
            mincost[S] = 0;
            boolean[] vis = new boolean[V];
            for (i = 0; i < V;   i) {
                if (!isV.contains(i)) vis[i] = true;
            }

            int sum = 0;
            while (true) {
                int v = -1;
                for (int u = 0; u < V;   u) {
                    if (!vis[u] && (v == -1 || mincost[v] > mincost[u])) v = u;
                }
                if (v == -1) break;
                sum  = mincost[v];
                vis[v] = true;
                for (int u = 0; u < V;   u) {
                    mincost[u] = Math.min(mincost[u], dist[v][u]);
                }
            }

            System.out.println(sum);
        }
    }

    void bfs(int S, int row, int col) {
        Queue<Integer> queue = new ArrayDeque<Integer>();
        Set<Integer> vis = new HashSet<Integer>();
        queue.offer(S);
        vis.add(S);

        int[][] dir = {{1, 0},{-1, 0},{0, 1},{0, -1}};
        int diff = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size;   i) {
                int now = queue.poll();
                int x = now / col;
                int y = now % col;
                if (map[x][y] == 'A') {
                    dist[S][now] = diff;
                    dist[now][S] = diff;
                }
                for (int[] d : dir) {
                    int nx = x   d[0];
                    int ny = y   d[1];
                    if (nx >= 0 && nx < row && ny >= 0 && ny < col && !vis.contains(nx * col   ny) && map[nx][ny] != '#') {
                        queue.offer(nx * col   ny);
                        vis.add(nx * col   ny);
                    }
                }
            }
            diff   ;
        }
    }
}

maze 地图

0 人点赞