Quân Xe Trên Bàn Cờ Vỡ
Points
38
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
graph
Đề bài
Cho một bàn cờ kích thước $R \times C$. Mỗi ô có thể là ô trống (.) hoặc ô bị chặn (#).
Bạn muốn đặt nhiều quân Xe nhất có thể lên các ô trống sao cho không có hai quân Xe nào ăn được nhau. Hai quân Xe ăn nhau nếu chúng nằm trên cùng một hàng hoặc cùng một cột và không có ô bị chặn # nào nằm giữa chúng.
Hãy tìm số lượng quân Xe nhiều nhất có thể đặt.
Dữ liệu vào
- Dòng đầu tiên chứa hai số nguyên $R, C$ ($1 \le R, C \le 200$).
- $R$ dòng tiếp theo, mỗi dòng gồm $C$ ký tự
.hoặc#.
Dữ liệu ra
- Một số nguyên duy nhất là số lượng quân Xe tối đa có thể đặt.
Ví dụ
Input
3 3
.#.
...
.#.
Output
3
Giải thích
Có thể đặt 3 quân Xe tại $(1,1)$, $(1,3)$ và $(2,2)$. Vì ô $(1,2)$ bị chặn nên $(1,1)$ không ăn $(1,3)$, và $(2,2)$ nằm khác hàng và khác cột với cả hai quân trên.
Giới hạn
- $1 \le R, C \le 200$
- Thời gian: 2 giây
- Bộ nhớ: 256 MB
Community Discussion