← 返回题目列表

Codeforces · 1202/C

C. 给你一个 WASD 字符串......

中文机器翻译题面 查看原题

你有一个字符串 $$$s$$$ — 玩具机器人的命令序列。机器人被放置在矩形网格的某个单元格中。他可以执行四个命令:

- 'W' — 向上移动一个单元格;
- 'S' — 向下移动一个单元格;
- 'A' — 向左移动一个单元格;
- 'D' — 向右移动一个单元格。

令 $$$Grid(s)$$$ 为最小可能区域的网格,这样网格中就有一个位置可以放置机器人,使其在运行命令序列 $$$s$$$ 时不会从网格上掉落。例如,如果 $$$s = \text{DSAWWAW}$$$ 则 $$$Grid(s)$$$ 是 $$$4 \times 3$$$ 网格:

1.您可以将机器人放置在单元格$$$(3, 2)$$$中;
2.机器人执行命令“D”并移动到$$$(3, 3)$$$;
3.机器人执行命令“S”并移动到$$$(4, 3)$$$;
4.机器人执行命令'A'并移动到$$$(4, 2)$$$;
5.机器人执行命令“W”并移动到$$$(3, 2)$$$;
6. 机器人执行命令“W”并移动到$$$(2, 2)$$$;
7. 机器人执行命令'A'并移动到$$$(2, 1)$$$;
8. 机器人执行命令“W”并移动到$$$(1, 1)$$$。

您有 $$$4$$$ 额外字母:1 个“W”、1 个“A”、1 个“S”、1 个“D”。您希望在序列 $$$s$$$ 的任意位置插入最多一个这些字母,以最小化 $$$Grid(s)$$$ 的面积。

您能达到的 $$$Grid(s)$$$ 的最小面积是多少?

输入

第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 1000$$$) — 查询数量。

接下来的 $$$T$$$ 行包含查询:每行一个。该行包含单个字符串 $$$s$$$ ($$$1 \le |s| \le 2 \cdot 10^5$$$, $$$s_i \in \{\text{W}, \text{A}, \text{S}, \text{D}\}$$$) — 命令序列。

保证所有查询的 $$$s$$$ 的总长度不超过 $$$2 \cdot 10^5$$$。

输出

打印 $$$T$$$ 整数:每个查询一个。对于每个查询,打印您可以实现的 $$$Grid(s)$$$ 的最小面积。

示例

输入 #1

3
DSAWWAW
D
WA

输出 #1

8
2
4

注意

在第一个查询中,您必须获取字符串 $$$\text{DSAWW}\underline{D}\text{AW}$$$。

在第二个和第三个查询中,您无法减少 $$$Grid(s)$$$ 的面积。