”Ґа¬Ґа „¦® аҐиЁ« гЄа бЁвм ¤®¬. Џ®бҐвЁў ЄЁв ©бЄЁ© ¬ Ј §ЁзЁЄ ® ис« б⥪«пго дЁЈгаЄг Є®а®ўл Ё аҐиЁ« Ґс ЄгЇЁвм.
”®а¬ Є®а®ўл ®ЇЁблў Ґвбп аҐисвЄ®© Ё§ \(N \times M\) (\(3 \leq N, M \leq 500\)) бЁ¬ў®«®ў ( аЁбгЄҐ Ё¦Ґ ЇаЁўҐ¤Ґ ЇаЁ¬Ґа). ђ §«ЁзлҐ бЁ¬ў®«л (¬Ґ«ҐмЄЁҐ « вЁбЄЁҐ) ®Ў®§ з ов а §«ЁзлҐ жўҐв , бЁ¬ў®« '.' - ®вбгвбвўЁҐ дЁЈгал.
...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa...
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............
Љ Ґбз бвмо ¤® Ї®ЄгЇЄЁ ў ¬ Ј §ЁзЁЄ ў®аў «бп ЎлЄ, ўбс а §Ја®¬Ё« Ё б«®¬ « дЁЈгаЄг ”„ ваЁ з бвЁ, Є®в®алҐ § вҐап«Ёбм Ї®«г б।Ё \(K\) (\(4 \leq K \leq 100\)) ¤агЈЁе ЄгбЄ®ў Ї®«г. Љ ¦¤л© Ё§ \(K\) ЄгбЄ®ў Ї®«г ®ЇЁблў Ґвбп «®ЈЁз® ⮬㠪 Є н⮠ᤥ« ® ўлиҐ.
Џ®¬®ЈЁвҐ ”„ ®ЇаҐ¤Ґ«Ёвм бЄ®«мЄ® Ў®а®ў Ё§ 3 ЄгбЄ®ў (Ё§ \(K\) ў «пойЁебп Ї®«г)
¬Јгв б®бв ўЁвм б«®¬ го дЁЈгаг.
ЉгбЄЁ Ї®«г ¬®Јгв ЇҐаҐ¬Ґй вмбп Ј®аЁ§®в «м® Ё ўҐавЁЄ «м®, ЇҐаҐў®а зЁў вмбп Ј®аЁ§®в «м® Ё ўҐавЁЄ «м®, в Є¦Ґ Ї®ў®а зЁў вмбп Є®«ЁзҐбвў® Ја ¤гб®ў, Єа ⮥ 90.
ЋЁ ¤®«¦л б®бв ўЁвм в®з® Ёб室го дЁЈгаЄг Є ¦¤ п Ї®§ЁжЁп ¤®«¦ Ўлвм ЇаҐ¤бв ў«Ґ а®ў® ®¤Ё¬ ЄгбЄ®¬.
”ЋђЊЂ’ ‚‚Ћ„Ђ (д ©« bcs.in):
ЏҐаў п бва®Є ᮤҐа¦Ёв ®¤® 楫®Ґ зЁб«®
\(K\). „ «ҐҐ Ё¤св
\(K + 1\) ®ЇЁб Ё©.
ЏҐаў®Ґ ®ЇЁблў Ґв ®аЁЈЁ «мго дЁЈгаЄг, ®бв «млҐ
\(K\) - ®ЇЁб ЁҐ ЄгбЄ®ў Ї®«г.
Љ ¦¤®Ґ ®ЇЁб ЁҐ зЁ Ґвбп б® бва®ЄЁ, ᮤҐа¦ 饩 ¤ў 楫ле зЁб« \(R\) Ё \(C\)
(\(1 \le R, C \le 100\)). Џ®б«Ґ¤гойЁҐ \(R\) бва®Є ᮤҐа¦ в Ї® \(C\) ¬ «ҐмЄЁе « вЁбЄЁе бЁ¬ў®«®ў, ®ЇЁблў ойЁе 梥⠪ ¦¤®© п祩ЄЁ. Љ ¦¤л© Єгб®Є ᮥ¤ЁпҐвбп Ј®аЁ§®в «м® Ё«Ё ўҐавЁЄ «м® Ё Ё¬ҐҐв е®вп Ўл ®¤г Ґ-Їгбвго п祩Єг.
”ЋђЊЂ’ ‚›‚Ћ„Ђ (д ©« bcs.out):
‚뢥¤ЁвҐ Є®«ЁзҐбвў® ваЁЇ«Ґв®ў \(i, j, k\) (\(i < j < k\)) в ЄЁе, зв® ЄгбЄЁ \(i\), \(j\),
Ё \(k\) ¬®Јгв б®бв ўЁвм Ёб室го дЁЈгаЄг Є®а®ўл.
Џђ€Њ…ђ ‚‚Ћ„Ђ:
5
5 5
aaaaa
..a..
bbabb
..a..
aaaaa
3 5
..abb
..a..
aaaaa
5 2
a.
a.
aa
a.
a.
1 2
bb
1 5
bbabb
2 5
aaaaa
..a..
Џђ€Њ…ђ ‚›‚Ћ„Ђ:
3
ќвЁ ваЁ аҐиҐЁп ЁбЇ®«м§гов ЄгбЄЁ \((0, 1, 2)\), \((0, 2, 4)\), \((1, 3, 4)\).
‡ ¬ҐвЁ¬, зв® нв § ¤ з Ё¬ҐҐв 6 ᥪ㤠вҐбв ( ¤«п ЏЁв® Ё Java - 12)
Ђўв®а : Brian Dean
Farmer John has decided his home needs more decoration. Visiting the local
china shop, he finds a delicate glass cow figurine that he decides to purchase,
knowing that it will fit perfectly on the mantel above his fireplace.
The shape of the cow figurine is described by an \(N \times M\) grid of characters
like the one below (\(3 \leq N, M \leq 500\)), where lowercase letter characters
are each part of the figurine (indicating different colors) and '.' characters
are not.
...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa...
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............
Unfortunately, right before FJ can make his purchase, a bull runs through the
shop and breaks not only FJ's figurine, but many of the other glass objects on
the shelves as well! FJ's figurine breaks into 3 pieces, which quickly become
lost among \(K\) total pieces lying on the ground (\(4 \leq K \leq 100\)). Each of
the \(K\) pieces is described by a grid of characters, just like the original
figurine.
Please help FJ determine how many sets of 3 pieces (out of the \(K\) on the floor)
could be glued back together to mend his broken figurine.
The pieces on the ground might have been flipped vertically or horizontally, or
rotated by some multiple of 90 degrees. Therefore, given the original grid as
well as \(K\) grids describing pieces, you want to find sets of 3 pieces that can
be joined together to form the original picture, allowing the pieces to be
translated, flipped, or rotated multiples of 90 degrees. When then
superimposed, the 3 pieces should exactly form the original picture, with each
colored square in the original picture represented in exactly one of the pieces.
Формат входных данных:
The first line contains a single integer
\(K\). Following that will be
\(K + 1\)
piece descriptions. The first description will describe the original glass cow,
the following
\(K\) descriptions will be of the broken pieces.
Each description begins with a line containing two integers \(R\) and \(C\)
(\(1 \le R, C \le 100\)). The following \(R\) lines contain \(C\) lowercase alphabet
characters describing the color of each cell. Each piece will be
horizontally/vertically connected and have at least one non-empty cell.
Формат выходных данных:
Output the number of triples \(i, j, k\) (\(i < j < k\)) such that pieces \(i\), \(j\),
and \(k\) can be arranged to form the original glass cow.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 5
aaaaa
..a..
bbabb
..a..
aaaaa
3 5
..abb
..a..
aaaaa
5 2
a.
a.
aa
a.
a.
1 2
bb
1 5
bbabb
2 5
aaaaa
..a..
|
3
|