먼 목초지

농부 존(Farmer John)의 농장은 N x N 격자의 목초지로 이루어져 있으며, 각 목초지에는 서로 다른 두 종류의 풀 중 하나가 자란다. 이 두 종류의 풀을 나타내기 위해 문자 (와 )를 사용한다.

소 베시(Bessie)가 농장을 돌아다닐 때, 같은 종류의 풀이 자라는 인접한 목초지(북, 남, 동, 서로 한 칸)로 이동하는 데는 A 단위의 시간이 걸리고, 다른 종류의 풀이 자라는 인접한 목초지로 이동하는 데는 B 단위의 시간이 걸린다. 베시가 한 목초지에서 먼 목초지로 이동할 때는 항상 시간이 최소가 되는 이동 순서를 사용한다. 농장의 어떤 목초지 쌍 사이를 이동할 때 베시에게 필요한 시간의 최댓값을 계산하시오.

첫째 줄: 세 정수 N (1 <= N <= 30), A (0 <= A <= 1,000,000), B (0 <= B <= 1,000,000).

둘째 줄부터 N+1번째 줄까지: 각 줄에 길이 N의 괄호 문자열이 주어진다. 이 N개의 줄이 모여 N x N 괄호 격자를 이룬다.

베시가 어떤 목초지 쌍 사이를 이동하는 데 쓸 수 있는 시간의 최댓값을 나타내는 정수 하나 (베시는 항상 시간이 최소인 경로를 따른다).

riseoj 작성

출처 올림피아드 > USACO > 2012-2013 > November > Silver