trang chủ / đề bài / icpc22_mt_f

Vòng tay giấy

Đề bài

Mô tả

Alice làm vòng tay bằng giấy bằng cách dán hai đầu của một dải giấy dài lại với nhau. Trên dải giấy có k hình vẽ (1≤k≤6), mỗi hình vẽ là một ô vuông 3×3, các hình vẽ đặt liền nhau thành một hàng; mỗi ô 1×1 của hình vẽ là ký tự o (được tô) hoặc . (để trống). Dải giấy được viền bằng ký tự #: khi đặt nằm ngang, dải giấy là một hình chữ nhật 5×(4k+1) có hàng 1, hàng 5 và các cột 1,5,9,…,4k+1 toàn là #, còn k khối 3×3 nằm giữa các cột đó là k hình vẽ theo thứ tự từ trái sang phải. Ví dụ hai dải giấy có 3 và 4 hình vẽ:

#############
#.o.#...#...#
#.o.#...#...#
#.o.#...#...#
#############

#################
#ooo#ooo#ooo#ooo#
#...#...#...#...#
#ooo#ooo#ooo#ooo#
#################

Khi dán, mặt có hình vẽ luôn ở phía ngoài. Vòng tay là một vòng khép kín nên không có hình vẽ nào là "đầu tiên", và vòng tay có thể bị lật ngược khi so sánh. Cụ thể, hai vòng tay được coi là giống nhau nếu chúng có cùng số hình vẽ và dải giấy (nằm ngang) của vòng này biến được thành dải giấy của vòng kia bằng các thao tác:

  • chuyển hình vẽ đầu tiên (bên trái) xuống cuối dải, làm bao nhiêu lần tùy ý;
  • xoay cả dải giấy 180∘ (tức là đảo thứ tự các hình vẽ và xoay mỗi hình vẽ 180∘).

Ví dụ thứ hai có bốn dải giấy, mỗi dải 3 hình vẽ. Dải thứ nhất có cột o ở mép trái hình vẽ đầu tiên, hai hình còn lại trống. Xoay dải này 180∘ được dải có cột o ở mép phải hình vẽ cuối, rồi chuyển hình vẽ đầu xuống cuối hai lần thì được đúng dải thứ hai. Chuyển hình vẽ đầu của dải thứ nhất xuống cuối hai lần thì được dải thứ ba. Vậy ba dải đầu tạo ra ba vòng tay giống nhau, còn dải thứ tư (cột o ở giữa) tạo ra một loại khác.

Alice thiết kế nhiều dải giấy trên một tờ giấy lớn kích thước n×m rồi cắt rời từng dải để dán. Mỗi dải giấy trên tờ giấy lớn được đặt nằm ngang (kích thước 5×(4k+1)) hoặc nằm dọc (kích thước (4k+1)×5, các hình vẽ xếp từ trên xuống dưới). Dải nằm dọc được xoay 90∘ thành nằm ngang trước khi dán; xoay theo chiều nào cũng cho cùng một loại vòng tay vì hai cách xoay chỉ khác nhau một phép xoay 180∘. Dải chỉ có một hình vẽ (kích thước 5×5) được dán nằm ngang, đúng như hình vẽ trên giấy. Các dải giấy không chồng lên nhau nhưng có thể nằm sát cạnh nhau.

Hãy đếm số loại vòng tay khác nhau, và với mỗi loại, đếm số vòng tay thuộc loại đó.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n và m (1≤n,m≤1000).

Mỗi dòng trong n dòng tiếp theo chứa m ký tự, mỗi ký tự là ., # hoặc o. Ký tự # và o chỉ dùng để vẽ các dải giấy; ký tự . nằm ngoài các dải giấy là ô trống.

Dữ liệu đảm bảo:

  • tờ giấy chỉ gồm các dải giấy hoàn chỉnh, không có ký tự # hay o nào thừa, và có ít nhất một dải giấy;
  • mỗi dải giấy có không quá 6 hình vẽ;
  • mọi khối 3×3 không chứa ký tự # mà viền 5×5 bao quanh nó toàn là # đều là một hình vẽ của một dải giấy.

Dữ liệu ra

Dòng đầu tiên in ra số loại vòng tay t.

Dòng thứ hai in ra t số nguyên là số vòng tay của từng loại, theo thứ tự tăng dần.

Ràng buộc

  • 1≤n,m≤1000.
  • Mỗi dải giấy có từ 1 đến 6 hình vẽ.

Ví dụ

Input Output Giải thích
23 28
............................
.#############.##########...
.#o..#...#...#.#o.o##o.o#...
.#o..#...#...#.#.o.##.o.#...
.#o..#...#...#.#o.o##o.o#...
.#############.##########...
....................#o.o#...
.#################..#.o.#...
.#ooo#ooo#ooo#ooo#..#o.o#...
.#...#...#...#...#..#####...
.#ooo#ooo#ooo#ooo#..#o.o#...
.#################..#.o.#...
.#############......#o.o#...
.#..o#...#...#......#####...
.#..o#...#...##############.
.#..o#...#...##.o.#...#...#.
.##############.o.#...#...#.
.##############.o.#...#...#.
.#...#o..#...##############.
.#...#o..#...#..............
.#...#o..#...#..............
.#############..............
............................
5
1 1 1 1 3
Có 7 vòng tay. Ba dải có cột o ở mép trái hình đầu, mép phải hình đầu, hoặc mép trái hình thứ hai là cùng một loại; bốn dải còn lại (một hình chữ X, ba hình chữ X xếp dọc, bốn hình ooo, và dải có cột o ở giữa) mỗi dải một loại.
5 55
#############.#############.#############.#############
#o..#...#...#.#..o#...#...#.#...#o..#...#.#.o.#...#...#
#o..#...#...#.#..o#...#...#.#...#o..#...#.#.o.#...#...#
#o..#...#...#.#..o#...#...#.#...#o..#...#.#.o.#...#...#
#############.#############.#############.#############
2
1 3
Ba dải đầu giống nhau, dải thứ tư khác.

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