Bàn cờ trắng đen

View as PDF

Submit solution

Points: 1.00 (partial)
Time limit: 2.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Cho một bàn cờ ~n \times n~. Các hàng được đánh số từ ~1~ tới ~n~ từ trên xuống dưới, các cột được đánh số từ ~1~ tới ~n~ từ trái qua phải (Ô ~(1, 1)~ là góc trái trên và ~(n, n)~ là góc phải dưới).

Trên một số ô của bàn cờ có chứa một quân cờ mang màu trắng hoặc đen (số còn lại không chứa gì), quân cờ ở ô ~(i, j)~ có giá trị là ~w_{ij}~.

Nhiệm vụ của bạn là bốc được hết các quân cờ ra khỏi bàn cờ. Tại mỗi bước, bạn có thể chọn một quân cờ trắng ~u~ một quân cờ đen ~v~ và xóa chúng ra khỏi bàn cờ trong thời gian ~|w_u - w_v|~. Tuy nhiên, một quân cờ ~(x, y)~ chỉ được phép chọn ở thao tác này nếu hiện tại không có quân cờ ~(x_1, y_1)~ nào khác mà ~x_1 \geq x~ và ~y_1 \leq y~.

Ngoài ra, bạn cũng có thể chọn một quân cờ ~u~ bất kỳ trên bàn cờ và đưa nó ra khỏi bàn trong thời gian ~w_u~.

Bạn hãy tính thời gian ngắn nhất có thể để đưa hết cờ ra khỏi bàn.

Input

Dòng đầu chứa một số nguyên dương ~n (1 \leq n \leq 12)~.

~n~ dòng tiếp theo mỗi dòng chứa một xâu gồm ~n~ ký tự ".", "W" hoặc "B" biểu diễn một ô trống, một ô chứa cờ trắng hoặc một ô chứa cờ đen.

~n~ dòng tiếp theo mỗi dòng chứa một dãy ~n~ số nguyên dương. Số nguyên dương thứ ~j~ của dòng thứ ~i~ là giá trị ~w_{ij} (0 \leq w_{ij} \leq 10^{6}).~

Oụtput

In ra một số nguyên duy nhất là thời gian ngắn nhất để chuyể hết các quân cờ ra khỏi bàn.

Sample Input 1

4
WBB.
BWBW
WBWW
BBBW
1 1 1 0
1 1 1 1
1 1 1 1
1 1 1 1

Sample Output 1

3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.