TPBISHOP - Quân tượng

• Thời gian: 0.11s
• Bộ nhớ: 1536MB
• Mã nguồn: 50000 bytes

Cho 1 bàn cờ kích thước NxN. Hãy đếm số quân tượng nhiều nhất có thể đặt lên bàn cờ sao cho cùng lúc không có 2 quân tượng nào ăn được nhau. Quân tượng đi theo luật cờ vua thông thường với ngoại lệ: chúng không thể thực hiện nước đi dài quá 1 ô. Nói cách khác, nếu quân tượng đang đứng ở ô (u,v) thì có thể đi được đến ô (u ±1,v ±1).

Ngoài ra 1 số ô của bàn cờ có vật cản và không thể đặt quân cờ lên.

Input

• Dòng đầu số N (1 <= N <= 50)
• N dòng sau mỗi dòng N kí tự mô tả bàn cờ. Kí tự '*' thể hiện ô có vật cản, kí tự '.' thể hiện ô trống.

Output

Số quân tượng nhiều nhất có thể đặt lên bàn cờ

Sample input

3

*.*

.*.

***

Sample output

2

• Người up: dat1511
• Nguồn bài: Khúc Anh Tuấn