题目描述

DFS+曼哈顿距离(Math.abs(x1 - x2) + Math.abs(y1 - y2))

样例

import java.util.*;

class Main {

    static class Pair {
        int x, y;

        Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    //dx和dy代表偏移量数组 用来枚举左上右下四个方向
    static final int[] dx = {-1, 0, 1, 0};
    static final int[] dy = {0, 1, 0, -1};

    static int N = 55;
    static char[][] g = new char[N][N];
    static ArrayList<Pair>[] points;

    //x和y表示当前的坐标，ps表示当前存在哪个points里面
    static void dfs(int x, int y, ArrayList<Pair> ps) {

        //把当前的点放入points中
        ps.add(new Pair(x, y));
        //搜索到了x,就把变成. 一边搜x,一边把x变.
        g[x][y] = '.';


        //枚举上右下左四个方向
        for (int i = 0; i < 4; i++) {
            int a = x + dx[i], b = y + dy[i];
            //如果发现当前位置没有越界，并且下一个位置为x
            if (a >= 0 && a < g.length && b >= 0 && b < g[0].length && g[a][b] == 'X')
                //那就dfs这个格子
                dfs(a, b, ps);
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();

        //当你使用 nextInt()等方法读取基本类型时，输入缓冲区中的换行符可能会留在缓冲区中，
        //如果不消耗这个换行符，后续的 nextLine() 将会读取到一个空行。
        //因此，在读取完整数后，调用scanner.nextLine().
        //可以确保输入缓冲区中的换行符被消耗掉，以便后续的 nextLine() 可以正常读取下一行的输入。
        scanner.nextLine();

        points = new ArrayList[2];
        points[0] = new ArrayList<>();
        points[1] = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            String line = scanner.nextLine();
            for (int j = 0; j < m; j++) {
                g[i][j] = line.charAt(j);
            }
        } 

        //k表示处理到第几块了
        int k = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                //如果发现当前位置是x,那我们就把相邻的x全都找出来，k++表示处理下一个块
                if (g[i][j] == 'X') {
                    dfs(i, j, points[k++]);
                }
            }
        }

        int res = Integer.MAX_VALUE;
        //从第一个点集当中随意取一个点
        for (Pair a : points[0]) {
            //从第二个点集当中随意取一个点
            for (Pair b : points[1]) {
                //去算曼哈顿距离，找到最小的    由于是点的数量 所以要减1
                res = Math.min(res, Math.abs(a.x - b.x) + Math.abs(a.y - b.y) - 1);
            }
        }

        System.out.println(res);
    }
}