2026-09-25：移动后的最大曼哈顿距离。用go语言，给定一个仅包含 U、D、L、R、_ 这几种字符的字符串 moves。
起始位置是二维坐标 (0, 0)。每读到一个字符，就进行一次移动：
U 表示纵坐标增加 1。
D 表示纵坐标减少 1。
L 表示横坐标减少 1。
R 表示横坐标增加 1。
_ 是一个可自由选择的占位符，每个下划线都可以单独改成 U、D、L、R 中的任意一种。
把字符串中的所有移动都执行完之后，会到达某个终点。要求求出这个终点到起始点 (0, 0) 的曼哈顿距离可能达到的最大值。
曼哈顿距离的计算方式是：对于两个点 (x1, y1) 和 (x2, y2)，距离等于 |x1 – x2| + |y1 – y2|。
1 <= moves.length <= 100000。
moves 仅由 ‘U’、‘D’、‘L’、‘R’ 和 ‘_’ 组成。
输入： moves = “L_D_”。
输出： 4。
解释：
一种最优选择为：
‘L’：(0, 0) -> (-1, 0)
将 ‘_’ 视为 ‘D’：(-1, 0) -> (-1, -1)
‘D’：(-1, -1) -> (-1, -2)
将 ‘_’ 视为 ‘L’：(-1, -2) -> (-2, -2)
最终位置到原点的曼哈顿距离为 |0 – (-2)| + |0 – (-2)| = 4。
题目来自力扣3968。
大体步骤如下：
一开始，把当前位置看作原点，也就是横坐标和纵坐标都从 0 开始。同时准备一个计数，用来记录遇到了多少个下划线字符。
然后从左到右依次读取字符串中的每一个字符。读取过程中，只处理已经明确的移动方向，而下划线先不决定具体方向。
如果当前字符是 L，就让横坐标减少 1，纵坐标不变。
如果当前字符是 R，就让横坐标增加 1，纵坐标不变。
如果当前字符是 D，就让纵坐标减少 1，横坐标不变。
如果当前字符是 U，就让纵坐标增加 1，横坐标不变。
如果当前字符是下划线，就暂时不改变横纵坐标，只把“自由移动次数”加一。
这样完整扫描一遍字符串之后，所有非下划线字符造成的最终横纵坐标已经确定下来，记作一个基础终点。所有下划线还没有分配方向，但它们已经被统计成一个自由移动的总数。
接下来考虑这些下划线怎样选择方向，才能让最终位置离原点尽可能远。曼哈顿距离等于最终横坐标的绝对值加上最终纵坐标的绝对值。每把一个下划线分配到横坐标方向或者纵坐标方向，都可以让它沿着当前坐标绝对值增大的方向移动。
也就是说，如果当前横坐标是正的，就可以把下划线选成 R，让横坐标更大；如果当前横坐标是负的，就选成 L，让横坐标更小。纵坐标也是同样道理。
因此，每一个下划线字符最多能让曼哈顿距离增加 1，而且一定可以做到增加 1。所以所有下划线带来的总增益，正好等于下划线的数量。
于是，最终能够达到的最大曼哈顿距离，就是非下划线字符已经形成的固定终点到原点的曼哈顿距离，再加上所有下划线的数量。
用描述性说法就是：先算出固定移动造成的横坐标绝对值与纵坐标绝对值之和，再把这个和加上自由下划线的个数。
以题目中的例子 “L_D_” 来看：
- 读到 L，横坐标变成 -1，纵坐标仍是 0。
- 读到一个下划线，自由次数变成 1。
- 读到 D，纵坐标变成 -1。
- 又读到一个下划线，自由次数变成 2。
扫描结束后，固定部分到达 (-1, -1)，它到原点的曼哈顿距离是 1 + 1 = 2。自由下划线一共有 2 个，每个都能让距离再增加 1，所以最大距离是 2 + 2 = 4。这与题目给出的输出一致。
这个过程中，字符串只会被从头到尾扫描一次。每次处理一个字符时，只做一些判断和加减操作，不需要嵌套循环，也不需要额外保存复杂结构。
因此：
总的时间复杂度是 O(n)，其中 n 是字符串 moves 的长度。
总的额外空间复杂度是 O(1)，因为除了输入字符串本身之外，只使用了常数个额外变量来保存横坐标、纵坐标和自由下划线数量。
Go完整代码如下：
package main
import (
"fmt"
)
func maxDistance(moves string) int {
x, y, free := 0, 0, 0
for _, ch := range moves {
switch ch {
case 'L':
x—
case 'R':
x++
case 'D':
y—
case 'U':
y++
default:
free++
}
}
return abs(x) + abs(y) + free
}
func abs(x int) int {
if x < 0 {
return –x
}
return x
}
func main() {
moves := "L_D_"
result := maxDistance(moves)
fmt.Println(result)
}
Python完整代码如下：
# -*-coding:utf-8-*-
def max_distance(moves: str) –> int:
x = 0
y = 0
free = 0
for ch in moves:
if ch == 'L':
x -= 1
elif ch == 'R':
x += 1
elif ch == 'D':
y -= 1
elif ch == 'U':
y += 1
else:
free += 1
return abs(x) + abs(y) + free
if __name__ == "__main__":
moves = "L_D_"
result = max_distance(moves)
print(result)
C++完整代码如下：
#include <iostream>
#include <string>
#include <cstdlib>
int maxDistance(const std::string& moves) {
int x = 0, y = 0, free = 0;
for (char ch : moves) {
switch (ch) {
case 'L':
—x;
break;
case 'R':
++x;
break;
case 'D':
—y;
break;
case 'U':
++y;
break;
default:
++free;
break;
}
}
return std::abs(x) + std::abs(y) + free;
}
int main() {
std::string moves = "L_D_";
int result = maxDistance(moves);
std::cout << result << std::endl;
return 0;
}
