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代码