Имеется текстовый экран из M строк и N столбцов (2<M, N<101). Первоначально экран заполнен дефисами.
На этом экране одна за другой рисуются прямоугольные рамки толщиной в один символ. Каждая рамка рисуется при помощи своего символа, являющегося заглавной буквой латинского алфавита. При рисовании рамки ее символы замещают на экране ранее изображенные. Рамки нарисованы таким образом, что у каждой из них видна хотя бы одна пара противолежащих углов.
Требуется по конечному изображению экрана определить, возможно ли однозначное восстановление последовательности рисования рамок.
В качестве результата необходимо получить:
- требуемую последовательность (если восстановление однозначно);
- два различных варианта последовательности (если восстановление не однозначно).
Примеры экранов.
14 31
-------------------------------
-AAAAAAAAAAAAAAAAAAAAAAAAAAAAA-
-A---------------------------A-
-A--HHHHHHHHHHHHHHHHHHHHHHHHHH-
-A--H------------------------H-
-A--H----GGGGGGGGGGGGGGGGGGGGG-
-A--H----G-------------------G-
-A--H----G----IIIIIIIIIIIIIIII-
-A--H----G----I--------------I-
-A--H----G----I--------------I-
-A--H----G----I--------------I-
-A--H----G----I--------------I-
-AAAHHHHHGGGGGIIIIIIIIIIIIIIII-
-------------------------------
20 45
---------------------------------------------
-AAAAAAAAAAAAAAAAAAAAAAAAAAAAA---------------
-A---------------------------A---------------
-A---------------------------A---------------
-A---------------------------A---------------
-A---------------------------A---------------
-A---------------------GGGGGGGGGGGGGGGGGGGGG-
-A---------------------G-----A-------------G-
-A---------------------G-----A-------------G-
-A---------------------G-----A-------------G-
-A---------------------G-----A-------------G-
-A---------------------G-----A-------------G-
-A---------------------G-----A-------------G-
-AAAAAAAAAAAAAAHHHHHHHHGGGGGGGGGGGGGGGGGGGGG-
---------------H--------------------H--------
---------------H--------------------H--------
---------------H--------------------H--------
---------------H--------------------H--------
---------------HHHHHHHHHHHHHHHHHHHHHH--------
---------------------------------------------
22 58
------SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSRRRRRRRR-------------
------S-----------------R-----------S-------R-------------
TTTTTTTTTTTTUUUUUUUUUUUUUUUUUUUUTTTTTTTTTTTTTTTTTT--------
T-----S-----U-----------R------U----S-------R----T--------
T-----S-----U-----------R------U----S-------R----T--------
T-----S-----U-----------R------U----S-------R----T--------
T-----S-----U-----------R------U----S-------R----T--------
TTTTTTTTTTTTUUUUUUUUUUUUUUUUUUUUTTTTTTTTTTTTTTTTTT--------
------S-----------------R-----------S-------R-------------
------S-----------------R-----------S-------R-------------
------S-----------------R-----------S-------R-------------
------SSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSQQQQQQQRQQQQQQQQQQQQQ
----------Q-------------R-------------------R------------Q
----------Q-------------R-------------------R------------Q
---VVVV---Q-------------R-------------------R------------Q
---V--V---Q-------------R-------------------R------------Q
---V--V---Q-------------R-------------------R------------Q
---V--V---Q-------------R-------------------R------------Q
---VVVV---Q-------------R-------------------R------------Q
----------Q-------------R-------------------R------------Q
----------Q-------------R-------------------R------------Q
----------QQQQQQQQQQQQQQRRRRRRRRRRRRRRRRRRRRRQQQQQQQQQQQQQ
24 76
----------------------------------------------------------------------------
-BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB--------------------
-B---IIIIIIIIIIIIIIIIIII-------------------------------B--------------------
-B---I-----------------I--------------------DDDDDDDDDDDDDDD-----------------
-B---I-----------------I--------------------D----------B--D-----------------
-B---I-----------------I----GGGGGGGGGGGGGGGGDGGG-------B--D-----------------
-B---I--------AAAAAAAAAIAAAAGAA-------------D--G-------B--D-----------------
-BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBDBBBBBBBBBBB-LLLLLLLLLLLLLL-----
-----I--------A--------I----G-A-------------D--G---------LD-----------L-----
-----I--------A-----HHHIHHHHGHHHHHHHH-------DDDDDDDDDDDDDLD-----------L-----
-----I--------A-----H--I----G-A-----H----------G---------L------------L-----
-----I--------A-----H--I----G-A-----H----------G---------L------------L-----
-----I--------A-----H--I----G-A-----H----------G---------L------------L-----
-----I--------A-----H--I----G-A-----H----------G---------L------------L-----
-----I--------AAAAAAHAAIAAAAGAA-----H----------G-------CCLCCCCCCCCCCCCLCCCC-
-----I--------------H--I----G-------H----------G-------C-L------------L---C-
-----IIIIIIIIIIIIIIIIIII----GGGGGGGGGGGGGGGGGGGG-------C-LLLLLLLLLLLLLL---C-
--------------------HHHHHHHHHHHHHHHHH------------------C------------------C-
-------------------------------------------------------C------------------C-
-------------------------------------------------------C------------------C-
-------------------------------------------------------C------------------C-
-------------------------------------------------------C------------------C-
-------------------------------------------------------CCCCCCCCCCCCCCCCCCCC-
----------------------------------------------------------------------------
18 38
--------------------------------------
-----------IIIIIIIIII-----------------
-----------I--------I-----------------
-AAAAAAAAAAIAAAAAAAAIAAAAAAAA---------
-A---------I--------I-------A---------
-A---------I--------I-------A---------
-A---------I--------I-------A---------
-A---------I--------I-------A---------
-A---------I--HHHHHHIHHHHHHHHHHHHHHHH-
-A---------I--H-----I-------A-------H-
-AAAAAAAGGGIIIIIIIIIIAAAAAAAA-------H-
--------G-----H-----G---------------H-
--------G-----H-----G---------------H-
--------G-----HHHHHHGHHHHHHHHHHHHHHHH-
--------G-----------G-----------------
--------G-----------G-----------------
--------GGGGGGGGGGGGG-----------------
--------------------------------------
21 38
--------------------------------------
-----------IIIIIIIIII-----------------
-----------I--------I-----------------
-AAAAAAAAAAIAAAAAAAAIAAAAAAAA---------
-A---------I--------I-------A---------
-A---------I--------I-------A---------
-A---------I--------I-------A---------
-A---------I--------I-------A---------
-A---------I--HHHHHHIHHHHHHHHHHHHHHHH-
-A---------I--H-----I-------A-------H-
-AAAAAAAGGGIIIIIIIIIIAAAAAAAA-------H-
--------G-----H-----G---------------H-
--------G-----H-----G---------------H-
--------G-----HHHHHHGHHHHHHHHHHHHHHHH-
--------G-----------G-----------------
--------G-----------G-----------------
--------GGGGGGGGGGGGBBBBBBB-----------
--------------------B-----B-----------
--------------------B-----B-----------
--------------------BBBBBBB-----------
--------------------------------------
17 37
-------------------------------------
-AAAAAAAAAAAAAAAAA-------------------
-A---------------A-------------------
-IIIIIIIIIIIIIIIIIGGGGGGGGGGGGGGG----
-I---------------I--------------G----
-I---------------I--------------G----
-IIIIIIIIIIIIIIIIBBBBBBBBBBBBBBBB----
-A---------------B--------------B----
-A---------------BBBBBBBBBBBBBBBB----
-AAAAAAAAAAAAAAAAGGGGGGGGGGGGGGGGHHH-
-----------------H-----------------H-
-----------------H-----------------H-
-----------------H-----------------H-
-----------------H-----------------H-
-----------------H-----------------H-
-----------------HHHHHHHHHHHHHHHHHHH-
-------------------------------------
21 51
---------------------------------------------------
-AAAAAAAAAAAAAAAAAAAAAAAA--------------------------
-A----------------------A--------------------------
-A----------------------A--------------------------
-A-----IIIIIIIIIIIIIIIIII--------------------------
-A-----I----------------I--------------------------
-A-----I----------------I--------------------------
-A-----I----------------I--------------------------
-A-----I----------------I--------------------------
-A-----I----------------I--------------------------
-A-----I----------------I--------------------------
-AAAAAAIIIIIIIIIIIIIIIIIIGGGGGGGGGGGGGGGHHHHHHHHHH-
------------------------G--------------G---------H-
------------------------G--------------G---------H-
------------------------G--------------G---------H-
------------------------G--------------G---------H-
------------------------G--------------G---------H-
------------------------G--------------G---------H-
------------------------GGGGGGGGGGGGGGGG---------H-
------------------------H------------------------H-
------------------------HHHHHHHHHHHHHHHHHHHHHHHHHH-
14 61
-------------------------------------------------------------
-AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA-
-A---------------------------------------------------------A-
-A---------HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH---------------A-
-A---------H-------------------------------H---------------A-
-A---------H-----GGGGGGGGGGGGGGGGGGGGG-----H---------------A-
-A---------H-----G-----BBBBBBBBBB----G-----H---------------A-
-A-----IIIIIIIIIIIIIIIIBIIIIIIIIBIIIIIIIIIIIIIII-----------A-
-A-----I---H-----G-----B--------B----G-----H---I-----------A-
-A-----I---H-----G-----B--------B----G-----H---I-----------A-
-A-----IIIIIIIIIIIIIIIIBIIIIIIIIBIIIIIIIIIIIIIII-----------A-
-A---------H-----G-----B--------B----G-----H---------------A-
-AAAAAAAAAAHHHHHHGGGGGGBBBBBBBBBBGGGGGHHHHHHAAAAAAAAAAAAAAAA-
-------------------------------------------------------------
