2022-11-24：小团在地图上放了3个定位装置，想依赖他们进行定位！ 地图是一个n*n的棋盘

2022-11-24：小团在地图上放了3个定位装置，想依赖他们进行定位！
地图是一个n*n的棋盘，
有3个定位装置(x1,y1),(x2,y2),(x3,y3)，每个值均在[1,n]内。
小团在(a,b)位置放了一个信标，
每个定位装置会告诉小团它到信标的曼哈顿距离，也就是对于每个点，小团知道|xi-a|+|yi-b|
求信标位置，信标不唯一，输出字典序最小的。
输入n，然后是3个定位装置坐标，
最后是3个定位装置到信标的曼哈顿记录。
输出最小字典序的信标位置。
1 <= 所有数据值 <= 50000。
来自美团。8.20笔试。题目2。

答案2022-11-24：

先找半径小的，小圆周要快些，宽度优先遍历。

代码用golang编写。代码如下：

package main

import (
    "fmt"
)

func main() {
    ans := find(3, []int{1, 1}, []int{3, 1}, []int{3, 4}, 3, 3, 2)
    fmt.Println(ans)
}

const MAX_VALUE = 1<<31 - 1

func find(n int, a, b, c []int, ad, bd, cd int) []int {
    var x1 []int
    r1 := MAX_VALUE
    var x2 []int
    r2 := 0
    var x3 []int
    r3 := 0
    if ad < r1 {
        x1 = a
        r1 = ad
        x2 = b
        r2 = bd
        x3 = c
        r3 = cd
    }
    if bd < r1 {
        x1 = b
        r1 = bd
        x2 = a
        r2 = ad
        x3 = c
        r3 = cd
    }
    if cd < r1 {
        x1 = c
        r1 = cd
        x2 = a
        r2 = ad
        x3 = b
        r3 = bd
    }
    // x1 r1     x2 r2 x3 r3
    cur := []int{x1[0] - r1, x1[1]}
    queue := make([][]int, 0)
    visited := make(map[string]struct{})
    ans := make([][]int, 0)
    queue = append(queue, cur)
    visited[fmt.Sprintf("%d_%d", cur[0], cur[1])] = struct{}{}

    for len(queue) > 0 {
        // cur x1为圆心，r1为半径的圆周上
        cur = queue[0]
        queue = queue[1:]
        if cur[0] >= 1 && cur[0] <= n && cur[1] >= 1 && cur[1] <= n && distance(cur[0], cur[1], x2) == r2 && distance(cur[0], cur[1], x3) == r3 {
            ans = append(ans, cur)
        }
        if len(ans) == 2 {
            break
        }
        add(cur[0]-1, cur[1]-1, x1, r1, &queue, visited)
        add(cur[0]-1, cur[1], x1, r1, &queue, visited)
        add(cur[0]-1, cur[1]+1, x1, r1, &queue, visited)
        add(cur[0], cur[1]-1, x1, r1, &queue, visited)
        add(cur[0], cur[1]+1, x1, r1, &queue, visited)
        add(cur[0]+1, cur[1]-1, x1, r1, &queue, visited)
        add(cur[0]+1, cur[1], x1, r1, &queue, visited)
        add(cur[0]+1, cur[1]+1, x1, r1, &queue, visited)
    }
    if len(ans) == 1 || ans[0][0] < ans[1][0] || (ans[0][0] == ans[1][0] && ans[0][1] < ans[1][1]) {
        return ans[0]
    } else {
        return ans[1]
    }
}

func add(x, y int, c []int, r int, queue *[][]int, visited map[string]struct{}) {
    key := fmt.Sprintf("%d_%d", x, y)
    _, ok := visited[key]
    if (distance(x, y, c) == r) && !ok {
        *queue = append(*queue, []int{x, y})
        visited[key] = struct{}{}
    }
}

func distance(x, y int, c []int) int {
    return abs(x-c[0]) + abs(y-c[1])
}

func abs(a int) int {
    if a < 0 {
        return -a
    } else {
        return a
    }
}

执行结果如下：

左神java代码

本作品采用《CC 协议》，转载必须注明作者和本文链接