题目描述

Farmer John's farm is made up of an $n \times n$ grid of pastures, where each pasture contains one of two different types of grass. To specify these two types of grass, we use the characters ( and ), so for example FJ's farm might look like the following grid:

(())
)()(
)(((
))))

When Bessie the cow travels around the farm, it takes her $A$ units of time to move from a pasture to an adjacent pasture (one step north, south, east, or west) with the same grass type, or $B$ units of time to move to an adjacent pasture with a different grass type. Whenever Bessie travels from one pasture to a distant pasture, she always uses a sequence of steps that takes the minimum amount of time. Please compute the greatest amount of time Bessie will ever need to take while traveling between some pair of pastures on the farm.

题目大意：给定一个 $n \times n$ 的一个网格，每个格子有一个字符，要么是 (，要么是 )。每个格子和它的上下左右的四个格子相邻，对于相邻的两个格子 $x$ 和 $y$，从 $x$ 走到 $y$ 的过程中，如果 $x$ 和 $y$ 中的字符相同，消耗 $A$ 单位时间，如果 $x$ 和 $y$ 中字符不同，消耗 $B$ 单位时间。定义点 $S$ 到点 $T$ 的时间为 $D(S,T)$，现在想请你求出网格中最大的 $D(S,T)$。

输入格式

第一行三个整数 $n,a,b$；

接下来 $n$ 行描述这个 $n\times n$ 的网格。

输出格式

一个整数，最大的 $D(S,T)$。

样例输入

3 1 2
(((
()(
(()

样例输出

5

提示

左上角到右下角所需的时间为 $5$，是最大值。

数据规模与约定

对于 $100\%$ 的数据，$1 \leq n \leq 30$，$1 \leq A \leq 1\times 10^6$，$1 \leq B \leq 1\times 10^6$。

题目来源

Silver