美团2022笔试第2题-定位

发表于 Changyan：

简介：

关键词：美团笔试；2022；探测器；定位；棋盘；DFS；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
public class Main {
    /**
     * 结果的x坐标
     */
    static int resx = Integer.MAX_VALUE;
    /**
     * 结果的y坐标
     */
    static int resy = Integer.MAX_VALUE;

    public static void main(String[] args){
        // 测试数据.注意题目给的坐标范围是[1, n]，这里将其左移至[0,n-1]
        // 测试数据的坐标系从0开始，为[0,n-1]，n为题目给的棋盘大小
        int n = 4;
        // 三个探测器 target 为  1,1，
        int x1 = 0, y1 = 0, d1 = 2;
        int x2 = 3, y2 = 0, d2 = 3;
        int x3 = 2, y3 = 3, d3 = 3;

        // 该表为三次dfs共享使用
        int[][] counts = new int[n][n];
        // 通过初始值为-1来避免target与探测器重合
        counts[x1][y1] = -1;
        counts[x2][y2] = -1;
        counts[x3][y3] = -1;

        // 每次 new 一个全为false的boolean[n][n]
        foo(x1, y1, d1, counts, new boolean[n][n]);
        foo(x2, y2, d2, counts, new boolean[n][n]);
        foo(x3, y3, d3, counts, new boolean[n][n]);

        System.out.println(resx + " " + resy);
    }

    /**
     * 从坐标 xy 开始dfs，标记
     */
    public static void foo(int x, int y, int distance, int[][] counts, boolean[][] visited) {
        // 越界
        if (x < 0 || x >= counts.length || y < 0 || y >= counts.length) {
            return;
        }
        // 已被访问过
        if (visited[x][y]) {
            return;
        }
        // 距离超了
        if (distance < 0) {
            return;
        }

        // 距离刚刚好，给该坐标点的counts值+1，表示该点被一个探测器标定。
        // 当值增到3，说明被3个探测器标定，该点就是备选结果。
        if (distance == 0) {
            counts[x][y] ++;
            if (counts[x][y] == 3) {
                getMinPoint(x, y);
            }
        }
        visited[x][y] = true;

        foo(x-1, y, distance - 1, counts, visited);
        foo(x+1, y, distance - 1, counts, visited);
        foo(x, y-1, distance - 1, counts, visited);
        foo(x, y+1, distance - 1, counts, visited);
    }
    private static void getMinPoint(int x, int y) {
        if (x < resx || y < resy) {
            resx = x;
            resy = y;
        }
    }
}