| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
DISPAST - Distant Pastures |
Nông trại của nông dân John (FJ) được thiết kế như một hình gồm N x N bãi cỏ, trong đó mỗi ô chứa một trong hai loại cỏ. Để biết hai loại cỏ này, chúng ta sử dụng dấu mở ngoặc đơn ‘(‘ và dấu đóng ngoặc đơn ‘)’. Một ví dụ về nông trại của FJ như sau:
(())
)()(
)(((
))))
Khi cô bò Bessie du lịch vòng quanh nông trại, cô ta mất A đơn vị thời gian để đi từ một bãi có qua một bãi cỏ kề đó (theo hướng đông, tây, nam, và bắc) nếu hai bãi cỏ có cùng một loại cỏ, và B đơn vị thời gian để đi qua bãi cỏ kề đó nếu hai bai cỏ không có cùng một loại cỏ. Bất kì khi nào Bessie du lịch từ bãi cỏ này qua bãi cỏ khác, cô ta luôn sử dụng một dãy bước có thời gian là nhỏ nhất. Hãy tính thời gian lớn nhất Bessie cần phải đi từ một bãi cỏ này tới bãi cỏ khác trong nông trại theo cách đi của cô.
Input
*Dòng 1: Gồm 3 số tự nhiên: N (1 <= N <= 30), A (0 <= A <= 1,000,000), và B (0 <= B <= 1,000,000).
*Dòng 1..N+1: Mỗi dòng chứa một chuỗi ngoặc đơn có độ dài N. Tổng cộng ta sẽ có N dòng để tạo thành bãi cỏ N x N bằng các dấu ngoặc đơn.
Output
*Dòng 1: Gồm một số tự nhiên là số lượng thời gian lớn nhất để Bessie dùng để đi du lịch giữa hai bãi cỏ bất kì (cô ta luôn chọn cách đi có thời gian nhỏ nhất giữa hai bãi cỏ).
Example
Input: 3 1 2 ((( ()( (() Output: 5
Bessie mất 5 đơn vị thời gian để đi từ góc trái trên để đi tới góc phải dưới. Không có cặp bãi cỏ nào khiến cô ta phải tốn nhiều thời gian hơn cặp bãi cỏ này.
| Được gửi lên bởi: | adm |
| Ngày: | 2013-01-23 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
