Nhân bản Nhân bản Nhfn bản
Đề bài
Mô tả
Chủ tập đoàn Automatic Cellular Manufacturing vừa được cấp bằng sáng chế cho một quy trình mới để sản xuất hàng loạt các chi tiết giống hệt nhau. Phương pháp của bà dùng một lưới ô vuông hai chiều, mỗi ô có một trong hai trạng thái: "trống" hoặc "đầy". Chi tiết cụ thể của quy trình đương nhiên là bí mật.
Ban đầu, một tập các ô trên lưới được tô đầy theo hình của chi tiết cần nhân bản. Qua một dãy các bước rời rạc, mọi ô trên lưới đồng thời cập nhật trạng thái bằng cách xét trạng thái của chính nó và của ô xung quanh. Nếu trong ô này có một số lẻ ô đầy thì ở bước tiếp theo ô đó đầy, ngược lại ô đó trống. Hình G.1 cho thấy vài bước của quá trình nhân bản với một mẫu đơn giản gồm ba ô đầy (bấm nút để xem từng bước).
grid .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... step Mẫu ban đầu highlight gray 5,6 6,5 6,6 step Sau bước 1 clear highlight gray 4,5 4,6 4,7 5,4 5,5 5,6 6,4 6,5 6,6 7,4 7,7 step Sau bước 2 clear highlight gray 3,4 3,6 3,8 4,3 4,4 4,5 4,6 4,7 4,8 5,4 5,6 5,8 6,3 6,4 6,5 6,6 6,7 6,8 7,4 7,6 7,8 8,3 8,4 8,5 8,6 8,7 8,8 step Sau bước 3 clear highlight gray 2,3 2,4 2,6 2,8 2,9 3,2 3,3 3,5 3,7 3,8 4,2 4,4 4,5 4,6 4,7 4,9 5,3 5,4 5,6 5,8 5,9 6,2 6,4 6,5 6,6 6,7 6,9 7,3 7,4 7,6 7,8 7,9 8,2 8,3 8,5 8,7 8,8 9,2 9,4 9,5 9,6 9,7 9,9 step Sau bước 4 clear highlight gray 1,2 1,6 1,10 2,1 2,2 2,5 2,6 2,9 2,10 5,2 5,6 5,10 6,1 6,2 6,5 6,6 6,9 6,10 9,2 9,6 9,10 10,1 10,2 10,5 10,6 10,9 10,10
Hình G.1: Quá trình nhân bản.
Tuy nhiên, một lỗi đã len vào quy trình. Sau mỗi bước cập nhật, có thể có một ô trên lưới tự đổi trạng thái. Ví dụ, Hình G.2 cho thấy điều có thể xảy ra nếu một ô bị đổi trạng thái sau bước thứ nhất và một ô khác bị đổi trạng thái sau bước thứ ba (ô bị đổi được tô đỏ).
grid .......... .......... .......... .......... .......... .......... .......... .......... .......... .......... step Mẫu ban đầu highlight gray 5,6 6,5 6,6 step Sau bước 1 (ô đỏ bị lật) clear highlight gray 4,5 4,6 4,7 5,4 5,5 5,6 6,5 6,6 7,4 7,7 highlight red 6,4 step Sau bước 2 clear highlight gray 3,4 3,6 3,8 4,3 4,4 4,5 4,6 4,7 4,8 5,3 5,5 5,6 5,8 6,6 6,7 6,8 7,3 7,5 7,6 7,8 8,3 8,4 8,5 8,6 8,7 8,8 step Sau bước 3 (ô đỏ bị lật) clear highlight gray 2,3 2,4 2,6 2,8 2,9 3,2 3,3 3,5 3,7 3,8 4,5 4,7 4,9 5,3 5,4 5,6 5,8 5,9 6,5 6,7 6,8 6,9 7,3 7,4 7,6 7,8 7,9 8,3 8,4 8,5 8,6 8,7 8,8 9,2 9,4 9,5 9,6 9,7 9,9 highlight red 6,8 step Sau bước 4 clear highlight gray 1,2 1,6 1,10 2,1 2,2 2,5 2,6 2,9 2,10 3,1 3,2 3,4 3,6 3,7 4,1 4,2 4,4 4,6 4,7 5,2 5,6 5,7 5,8 5,9 5,10 6,4 6,5 6,8 6,10 7,7 7,8 7,9 8,1 8,2 8,4 8,6 8,7 9,1 9,4 9,7 9,10 10,1 10,2 10,5 10,6 10,9 10,10
Hình G.2: Lỗi trong quá trình nhân bản. Hình này ứng với ví dụ 1.
Không may, các mẫu ban đầu đã bị mất, chỉ còn lại kết quả (có thể đã bị lỗi) của quá trình nhân bản. Hãy viết chương trình tìm một mẫu ban đầu khác rỗng nhỏ nhất có thể đã tạo ra mẫu cuối cùng cho trước.
Dữ liệu vào
Dòng đầu tiên chứa hai số nguyên và (, ), lần lượt là chiều rộng và chiều cao của hình chữ nhật bao của mẫu cuối cùng.
Tiếp theo là dòng, mỗi dòng gồm ký tự mô tả mẫu cuối cùng. Mỗi ký tự là . (ô trống) hoặc # (ô đầy). Có ít nhất một ô đầy ở hàng đầu tiên, ở hàng cuối cùng, ở cột đầu tiên và ở cột cuối cùng.
Dữ liệu ra
In ra một mẫu khác rỗng có kích thước nhỏ nhất có thể đã tạo ra mẫu đã cho, với giả thiết ở mỗi giai đoạn của quá trình nhân bản có tối đa một ô tự đổi trạng thái. Kích thước của một mẫu là diện tích hình chữ nhật bao của nó. Nếu có nhiều mẫu ban đầu khác rỗng có kích thước nhỏ nhất, in ra mẫu nào cũng được. Dùng ký tự . cho ô trống và # cho ô đầy. In mẫu với số hàng và số cột ít nhất cần thiết (tức là đúng hình chữ nhật bao của mẫu).
Ràng buộc
- .
- Mỗi hàng gồm đúng ký tự
.hoặc#; hàng đầu, hàng cuối, cột đầu và cột cuối đều có ít nhất một#.
Ví dụ
| Input | Output | Giải thích |
|---|---|---|
| 10 10 .#...#...# ##..##..## ##.#.##... ##.#.##... .#...##### ...##..#.# ......###. ##.#.##... #..#..#..# ##..##..## |
.# ## |
Đây là mẫu cuối cùng trong Hình G.2: bốn bước nhân bản từ mẫu gồm ba ô đầy, có lỗi sau bước và bước . |
| 8 8 ##..#.## #.####.# .#.#.#.. .##.#.## .#.#.#.. .##.#.## #..#.### ##.#.##. |
#### #..# #.## ###. |
Hai bước nhân bản từ mẫu này; sau bước thứ hai, ô ở hàng , cột bị đổi trạng thái. |
| 5 4 #.... ..### ..### ..### |
# | Một ô đầy sau một bước thành khối ô đầy; sau đó ô ở góc trên trái bị đổi thành đầy. |
Bình luận