P4441 [COCI 2017/2018 #3] Retro

小 Mirko 在圣诞节得到了一个视频游戏机。它不是 Playstation 4 或 Xbox one，而是 Atari 2600，并且附带了一个免费游戏。游戏的主角站在屏幕的底部，屏幕上其他地方有各种物体向底部掉落。 更确切地说，屏幕可以表示为一个由 R 行 S 列像素组成的网格。主角占据最底行的一个像素，并用 'M' 标记。其余像素用以下字符之一标记：'.'（空格）、'*'（炸弹）、'('（左括号）或 ')'（右括号）。 主角可以在一次移动中向左或向右移动一个像素，但不需要移动，而其他物体同时向下移动一个像素（可能移出屏幕）。当主角与一个括号处于同一位置时，我们说他拾取了该括号并将其添加到他已获得的括号数组的末尾。主角的目标是获得尽可能长的**有效**括号表达式。 有效的括号表达式通过以下方式递归定义： - "()" 是一个有效的表达式。 - 如果 **a** 是一个有效的表达式，那么 "(**a**)" 也是一个有效的表达式。 - 如果 **a** 和 **b** 是有效的表达式，那么 "**ab**" 也是一个有效的表达式。 当主角与炸弹处于同一位置时，或者当所有物体都掉出屏幕时，游戏结束。

输入的第一行包含正整数 R 和 S（1 ≤ R, S ≤ 300），表示屏幕的尺寸。 接下来的 R 行中的每一行包含 S 个字符 'M'、'.'、'*'、'(' 或 ')'，表示屏幕的初始状态。 测试数据将保证总是存在至少一个可以获得的有效括号表达式。

在第一行，你必须输出 Mirko 可以获得的最长有效括号表达式的长度。 在第二行，输出该表达式。如果存在多个最长的有效表达式，输出**字典序最小**的那个。

在价值 25% 总分的测试用例中，将满足 1 ≤ R ≤ 15。 在价值 50% 总分的测试用例中，将满足 1 ≤ R ≤ 100。 如果你输出了正确的长度，但表达式错误，你将获得该测试用例 40% 的分数。无论如何，为了得分，你的输出必须包含两行非空内容。 **第一个测试用例的说明**：主角的移动是：左，左，右，右。 **第二个测试用例的说明**：主角的移动是：保持不动，保持不动，保持不动，右，左。 **第三个测试用例的说明**：主角的移动是：保持不动，保持不动，右。 题面翻译由 ChatGPT-4o 提供。