trang chủ / bài tập / arthwall

Arthur và những bức tường

Cho mặt bằng một căn hộ là lưới $n \times m$ ô vuông. Mỗi ô vuông hoặc là tường (ký hiệu *) hoặc là ô trống (ký hiệu .).

Một căn phòng được định nghĩa là một thành phần liên thông cực đại gồm các ô trống, trong đó hai ô được coi là kề nhau khi chúng có chung một cạnh.

Bạn cần phá đi một số ít nhất các ô tường (đổi * thành .) sao cho sau khi phá, mọi căn phòng đều có hình chữ nhật (cạnh song song với cạnh lưới).

In ra mặt bằng căn hộ sau khi đã phá tường. Với bài toán này, tập các ô trống ở phương án tối ưu là duy nhất, nên đầu ra cũng là duy nhất.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $m$ — kích thước lưới.
$n$ dòng tiếp theo, mỗi dòng gồm $m$ ký tự * hoặc . mô tả mặt bằng ban đầu.

Dữ liệu ra

In ra $n$ dòng, mỗi dòng gồm $m$ ký tự — mặt bằng sau khi đã phá số tường ít nhất để mọi căn phòng đều là hình chữ nhật.

Ràng buộc

$1 \leq n, m \leq 2000$ .

Ví dụ

Input	Output	Giải thích
4 5 ..... ..... ..&ast;&ast;&ast; ..&ast;..	..... ..... ..... .....	Phá 4 ô tường để toàn bộ lưới trở thành một căn phòng hình chữ nhật $4 \times 5$ .
5 5 .&ast;.&ast;. &ast;&ast;&ast;&ast;&ast; .&ast;.&ast;. &ast;&ast;&ast;&ast;&ast; .&ast;.&ast;.	.&ast;.&ast;. &ast;&ast;&ast;&ast;&ast; .&ast;.&ast;. &ast;&ast;&ast;&ast;&ast; .&ast;.&ast;.	Bốn căn phòng $1 \times 1$ ban đầu đều đã là hình chữ nhật; không cần phá ô nào.
6 7 &ast;&ast;&ast;.&ast;.&ast; ..&ast;.&ast;.&ast; &ast;.&ast;.&ast;.&ast; &ast;.&ast;.&ast;.&ast; ..&ast;...&ast; &ast;&ast;&ast;&ast;&ast;&ast;&ast;	&ast;&ast;&ast;...&ast; ..&ast;...&ast; ..&ast;...&ast; ..&ast;...&ast; ..&ast;...&ast; &ast;&ast;&ast;&ast;&ast;&ast;&ast;	Sau khi phá, còn lại hai căn phòng hình chữ nhật: một cột bên trái và một khối $5 \times 3$ ở giữa.

Bình luận

Không có bình luận tại thời điểm này.

Nộp bài giải

Danh sách bài nộp Bài nộp tốt nhất

Điểm 8,00một phần

Giới hạn thời gian 2.0s

Giới hạn bộ nhớ 256M

Đầu vào stdin

Kết quả của bạn stdout

Dạng bài

Chưa phân loại

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig