Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

STRBALA2 - Chuỗi cân bằng 2

Mặc dù cô bò Bessie cho rằng mọi chuỗi cân bằng để thỏa mãn thẩm mỹ của ta, cô ta thích thú hơn với những chuỗi mà cô ta gọi là “tuyệt đối” cân bằng – gồm một chuỗi dấu mở ngoặc đơn ‘(‘ và được theo sau bởi một chuỗi dấu đóng ngoặc đơn ‘)’ với cùng một độ dài. Ví dụ:

(((())))
Một ngày nọ, trong lúc đi ngang qua cái chuồng, Bessie phát hiện ra một bảng gồm N x N ô có móng ngựa ở dưới đất, trong đó những móng ngưa được sắp xếp nên nó có hình dạng của dấu mở ngoặc đơn ‘(‘ hoặc dấu đóng ngoặc đơn ‘)’. Bắt đầu từ ô trái trên của bảng, Bessie muốn đi vòng để nhặt những cái móng ngựa sao cho chuỗi mà cô ta nhặt được là chuỗi tuyệt đối cân bằng. Hãy giúp cô ta đếm độ dài dài nhất của chuỗi tuyệt đối cân bằng mà cô ta có thể nhặt được.
Ở mỗi bước, Bessie có thể đi lên phía trên, dưới, trái, và phải. Cô ta chỉ có thể đi tới một ô có chứa một cái móng ngựa, và khi cô ta làm vậy, cô ta không thể trở về vị trí cũ được nữa (vị trí đó không còn móng ngựa). Cô ta bắt đầu nhặt các móng ngựa từ ô trái trên của bảng. Bessie chỉ nhặt những móng ngưạ để có thể tạo thành một chuỗi ngoặc tuyệt đối cân bằng, nên có thể cô ta không thể nhặt hết được tất cả các móng ngựa.Mặc dù cô bò Bessie cho rằng mọi chuỗi cân bằng để thỏa mãn thẩm mỹ của ta, cô ta thích thú hơn với những chuỗi mà cô ta gọi là “tuyệt đối” cân bằng – gồm một chuỗi dấu mở ngoặc đơn ‘(‘ và được theo sau bởi một chuỗi dấu đóng ngoặc đơn ‘)’ với cùng một độ dài. Ví dụ:

(((())))

Một ngày nọ, trong lúc đi ngang qua cái chuồng, Bessie phát hiện ra một bảng gồm N x N ô có móng ngựa ở dưới đất, trong đó những móng ngưa được sắp xếp nên nó có hình dạng của dấu mở ngoặc đơn ‘(‘ hoặc dấu đóng ngoặc đơn ‘)’. Bắt đầu từ ô trái trên của bảng, Bessie muốn đi vòng để nhặt những cái móng ngựa sao cho chuỗi mà cô ta nhặt được là chuỗi tuyệt đối cân bằng. Hãy giúp cô ta đếm độ dài dài nhất của chuỗi tuyệt đối cân bằng mà cô ta có thể nhặt được.

Ở mỗi bước, Bessie có thể đi lên phía trên, dưới, trái, và phải. Cô ta chỉ có thể đi tới một ô có chứa một cái móng ngựa, và khi cô ta làm vậy, cô ta không thể trở về vị trí cũ được nữa (vị trí đó không còn móng ngựa). Cô ta bắt đầu nhặt các móng ngựa từ ô trái trên của bảng. Bessie chỉ nhặt những móng ngưạ để có thể tạo thành một chuỗi ngoặc tuyệt đối cân bằng, nên có thể cô ta không thể nhặt hết được tất cả các móng ngựa.

Input

*Dòng 1: Một số tự nhiên N (2 <= N <= 5).

*Dòng 2..N+1: mỗi dòng chứa một chuối các dấu ngoặc có độ dài là N. Tổng cộng sẽ có N dòng thể hiện N x N ô chứa dấu ngoặc đơn.

Output

*Dòng 1: Độ dài dài nhất của chuỗi ngoặc tuyệt đối cân bằng từ các móng ngựa mà Bessie có thể nhặt được. Nếu Bessie không thể nhặt được một chuỗi cân bằng (nếu vị trí trái trên là một dấu đóng ngoặc đơn), xuất ra 0.

Example

Input:
4
(())
()((
(()(
))))

Output:
8

Dãy bước mà Bessie đi để được chuỗi tuyệt đối cân bằng có độ dài là 8 được diễn tả ở dưới:

1())
2)((
345(
876)

Được gửi lên bởi:adm
Ngày:2013-01-11
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

hide comments
2017-10-22 08:35:07
CODE AC C++ http://j.gs/9aG8
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.