版權聲明:本文為部落客原創文章,未經部落客允許不得轉載。 https://blog.csdn.net/u014688145/article/details/78964576
POJ 刷題系列:3026. Borg Maze
傳送門:3026. Borg Maze
題意:
給出一張迷宮圖,牆用”#”表示,起始點為”S”, 外星人為”A”,求從S出發,連通”A”的最短路徑。注意:”A”和”A”之間相連也算連通。
思路:
BFS + PRIME, 算比較綜合了,BFS為了求每個”A”之間的最短距離,接着PRIME求MST即可。需要注意,地圖中并非所有頂點有有效距離,是以把除A和S之外的頂點都當通路過,這樣可以避免求出這些無效頂點的距離。
代碼如下:
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 ++;
}
}
}
複制