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

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

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