会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
解题思路
两点曼哈顿距离 ∣r1−r2∣+∣c1−c2∣ 可以改写成
∣r1−r2∣+∣c1−c2∣=max(∣(r1+c1)−(r2+c2)∣,∣(r1−c1)−(r2−c2)∣)。
- 因此全局最大值一定出现在「r+c 最小与最大」或「r−c 最小与最大」这两对过道之间。
- 扫一遍地图，在
. 上维护这四个极值点。
- 比较两对的距离，输出较大的那一对。若所有过道的 r+c 都相同，两个和值点会重合，这时必须改用 r−c 那一对。
