题解 | 老子的意大利炮呢

import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int m = in.nextInt();
        int n = in.nextInt();
        int nums[][] = new int[m][n];
        for (int i = 0; i < m; i++) {
            String s = in.next();
            for (int j = 0; j < n; j++) {
                if (s.charAt(j) == '#') nums[i][j] = 1;
            }
        }
        int sx = in.nextInt() - 1;
        int sy = in.nextInt() - 1;
        int x1 = in.nextInt() - 1;
        int y1 = in.nextInt() - 1;
        int x2 = in.nextInt() - 1;
        int y2 = in.nextInt() - 1;
        int x3 = in.nextInt() - 1;
        int y3 = in.nextInt() - 1;
        int ex = in.nextInt() - 1;
        int ed = in.nextInt() - 1;
        int t1 = in.nextInt();
        int t2 = in.nextInt();
        int t3 = in.nextInt();
        int count[] = new int[3];
        Arrays.fill(count, -1);
        int min = Integer.MAX_VALUE;
        Deque<int[]> dq = new ArrayDeque<>();
        dq.offer(new int[] {ex, ed});
        nums[ex][ed] = 1;
        int dirs[][] = new int[][] {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
        int step = 0;
        int sum = 0;
        boolean flag = false;
        while (!dq.isEmpty()) {
            int size = dq.size();
            while (size-- > 0) {
                int num[] = dq.poll();
                int x = num[0];
                int y = num[1];
                if (x == x1 && y == y1) {
                    count[0] = step;
                    sum++;
                    if (sum == 3) {
                        flag = true;
                        break;
                    }
                } else if (x == x2 && y == y2) {
                    count[1] = step;
                    sum++;
                    if (sum == 3) {
                        flag = true;
                        break;
                    }
                } else if (x == x3 && y == y3) {
                    count[2] = step;
                    sum++;
                    if (sum == 3) {
                        flag = true;
                        break;
                    }
                }
                for (int dir[] : dirs) {
                    int dx = x + dir[0];
                    int dy = y + dir[1];
                    if (dx >= 0 && dx < m && dy >= 0 && dy < n && nums[dx][dy] == 0) {
                        nums[dx][dy] = 1;
                        dq.offer(new int[] {dx, dy});
                    }
                }
            }
            if (flag) break;
            step++;
        }
        for (int i = 0; i < 3; i++) {
            if (count[i] != -1) {
                int t = count[i] * (t1 + t2 + t3 + 1);
                if (i == 0) {
                    int x = Math.abs(sx - x2) + Math.abs(sy - y2);
                    int y = Math.abs(x3 - x2) + Math.abs(y3 - y2);
                    int z = Math.abs(x3 - x1) + Math.abs(y3 - y1);
                    int s1 = x + (t2 + 1) * y + (t2 + t3 + 1) * z;
                    x = Math.abs(sx - x3) + Math.abs(sy - y3);
                    z = Math.abs(x2 - x1) + Math.abs(y2 - y1);
                    int s2 = x + (t3 + 1) * y + (t2 + t3 + 1) * z;
                    t += Math.min(s1, s2);
                } else if (i == 1) {
                    int x = Math.abs(sx - x1) + Math.abs(sy - y1);
                    int y = Math.abs(x3 - x1) + Math.abs(y3 - y1);
                    int z = Math.abs(x3 - x2) + Math.abs(y3 - y2);
                    int s1 = x + (t1 + 1) * y + (t1 + t3 + 1) * z;
                    x = Math.abs(sx - x3) + Math.abs(sy - y3);
                    z = Math.abs(x2 - x3) + Math.abs(y2 - y3);
                    int s2 = x + (t3 + 1) * y + (t1 + t3 + 1) * z;
                    t += Math.min(s1, s2);
                } else {
                    int x = Math.abs(sx - x1) + Math.abs(sy - y1);
                    int y = Math.abs(x1 - x2) + Math.abs(y1 - y2);
                    int z = Math.abs(x3 - x2) + Math.abs(y3 - y2);
                    int s1 = x + (t1 + 1) * y + (t2 + t1 + 1) * z;
                    x = Math.abs(sx - x2) + Math.abs(sy - y2);
                    z = Math.abs(x3 - x1) + Math.abs(y3 - y1);
                    int s2 = x + (t2 + 1) * y + (t2 + t1 + 1) * z;
                    t += Math.min(s1, s2);
                }
                min = Math.min(min, t);
            }
        }
        System.out.println(min);
    }
}