trang chủ / đề bài / icpcwf17_g

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 8 ô xung quanh. Nếu trong 9 ô 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 w và h (1≤w≤300, 1≤h≤300), 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à h dòng, mỗi dòng gồm w 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

  • 1≤w,h≤300.
  • Mỗi hàng gồm đúng w 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 2×2 gồm ba ô đầy, có lỗi sau bước 1 và bước 3.
8 8
##..#.##
#.####.#
.#.#.#..
.##.#.##
.#.#.#..
.##.#.##
#..#.###
##.#.##.
####
#..#
#.##
###.
Hai bước nhân bản từ mẫu 4×4 này; sau bước thứ hai, ô ở hàng 1, cột 5 bị đổi trạng thái.
5 4
#....
..###
..###
..###
# Một ô đầy sau một bước thành khối 3×3 ô đầy; sau đó ô ở góc trên trái bị đổi thành đầy.

Bình luận

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

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0