P3057 [USACO12NOV] Distant Pastures S

农夫约翰的农场是一个 $N \times N$ 的牧场网格，每个牧场上种着两种不同种类的草之一。我们用字符 `(` 和 `)` 来表示这两种草，例如约翰的农场可能看起来像这样： ``` (()) )()( )((( )))) ``` 当奶牛贝茜在农场中移动时，从一个牧场移动到相邻的牧场（上、下、左、右一步）需要花费时间： - 如果两个牧场的草种类相同，花费 **$A$** 单位时间。 - 如果两个牧场的草种类不同，花费 **$B$** 单位时间。 当贝茜从一个牧场旅行到另一个较远的牧场时，她总是选择一条用时最短的路径。请计算：在所有可能的牧场对之间，按照最短路径行走所需时间的最大值。

- 第一行：三个整数 $N$（$1 \le N \le 30$）、$A$（$0 \le A \le 10^6$）和 $B$（$0 \le B \le 10^6$）。 - 接下来的 $N$ 行：每行包含一个长度为 $N$ 的括号字符串，共同构成一个 $N \times N$ 的括号网格。

- 一行：一个整数，表示贝茜在任意两个牧场之间旅行所需的最大时间（假设她总是走最短路径）。

**样例解释** 从左上角牧场到右下角牧场需要 $5$ 单位时间。没有其他牧场对需要比这更长的时间。 **数据范围** - $1 \le N \le 30$ - $0 \le A, B \le 10^6$