2022-11-24：小团在地图上放了 3 个定位装置，想依赖他们进行定位！地图是一个 n*n 的棋盘，有 3 个定位装置 (x1,y1),(x2,y2),(x3,y3)，每个值均在 [1,n] 内。小团在 (a,

2022-11-24
北京
本文字数：1336 字
阅读完需：约 4 分钟

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  }}