DÀN ĐÈN (7 ĐIỂM)CHO MỘT BẢNG KÍCH THƯỚC MXN ĐƯỢC CHIA THÀNH LƯỚ...

Tin học DE THI HSG TIN TINH QUANG NGAI

Bài 4. Dàn đèn (7 điểm)

Cho một bảng kích thước mxn được chia thành lưới ô vuông đơn vị, tại mỗi ô của bảng có

một trong các ký tự:



".": Ô trống.



"+": Ô có chứa một đèn chưa bật sáng.



"*": Ô có chứa một đèn đã bật sáng.

Hai đèn đã bật sáng bất kỳ không nằm cùng hàng hoặc cùng cột.

Yêu cầu: Hãy bật sáng thêm một số nhiều nhất các đèn sao cho: Số đèn sáng trên mỗi hàng

cũng như trên mỗi cột của bảng tối đa là 1.

Dữ liệu vào: Tệp văn bản DANDEN.INP



Dòng 1: Ghi hai số m, n (1  m, n  200) cách nhau một ký tự trắng



m dòng tiếp theo, dòng thứ i ghi n ký tự liên tiếp, ký tự thứ j là ký hiệu ô (i, j) của bảng

Dữ liệu ra: T

ệp

văn bản DANDEN.OUT



Dòng 1: Ghi số đèn có thể bật thêm



m dòng tiếp theo, dòng thứ i ghi n ký tự liên tiếp, ký tự thứ j là ký hiệu ô (i, j) của bảng sau

khi đã bật sáng thêm các đèn.

Ví dụ:

DANDEN.INP

DANDEN.OUT

4 5

+..*.

++.+.

*+.+.

.++..

.*+..

.+*..