TopView
SRM 550 · 2012-06-05 · by vexorian
SRM 550 · 2012-06-05 · by vexorian · Graph Theory, String Manipulation
Problem Statement
Problem Statement
Ralph was once playing with a set of cards and a grid of cells.
Each card was a rectangle of a unique color.
Different cards may have had different dimensions.
Ralph took his cards one at a time, and placed each of them onto the grid.
When placing a card, Ralph aligned its sides with grid lines, so each card covered some rectangular block of cells.
Some cards may have overlapped other, previously placed cards partially or even completely.
Once all the cards were placed, on each cell only the topmost card was visible.
You are given a String[] grid that describes what Ralph could see after placing the cards. The j-th character of element i of grid is '.' if the cell at position (i,j) is empty (does not contain any card) or is an alphanumeric character that represents the only color Ralph could see when looking at the cell.
Ralph does not remember the order he used to place the cards. Write a program that finds the order in which the cards of each visible color were placed. The return value should be aString , containing exactly once each of the alphanumeric characters that occur in grid.
The i-th character of the return value should be the color of the i-th card (0-based index) that Ralph placed.
In case there are multiple valid orders, return the lexicographically smallest one.
In case there is no valid order of colors, return "ERROR!" (quotes for clarity).
Ralph does not remember the order he used to place the cards. Write a program that finds the order in which the cards of each visible color were placed. The return value should be a
Notes
- The letters in grid are case-sensitive: 'a' and 'A' are distinct colors.
- The lexicographically smaller of two Strings of equal length is the one that has the earlier character (using ASCII ordering) at the first position at which they differ.
Constraints
- grid will contain between 1 and 50 elements, inclusive.
- Each element of grid will contain between 1 and 50 characters, inclusive.
- All elements of grid will contain the same number of characters.
- Each character in each element of grid will be a period ('.'), an uppercase letter ('A'-'Z'), a lowercase letter ('a'-'z'), or a digit ('0'-'9').
- At least one character in grid will be different from '.'.
Examples
0)
{"..AA..",
".CAAC.",
".CAAC."}
Returns: "CA"
The card with color C is a rectangle of 2 rows and 4 columns. The card with color A, a rectangle of 3 rows and 2 columns, was placed on top of it.
1)
{"..47..",
"..74.."}
Returns: "ERROR!"
Each card has a unique color, this top perspective view tells us about 2 cards. This setting is not possible without using multiple cards of color 4 or 7.
2)
{"bbb666",
".655X5",
"a65AA5",
"a65AA5",
"a65555"}
Returns: "65AXab"
3)
{"aabbaaaaaaaaaaaaaaaaaa",
"aabbccccccccccccccaaaa",
"aab11111ccccccccccaaaa",
"aab12221ccccccccccaaaa",
"aab12221ccccccccccaaaa",
"aab12221ccccccccccaaaa",
"aab12221ccccccccccaaaa",
"aab12221ccccccccccaaaa",
"aab12221ddddddddddaaaa",
"aab13331DDDDDDDDDDaaaa",
"aab13331DDDDDDDDDDaaaa",
"aa.11111DDDDDDDDDDaaaa",
"aaaaaaaaaaaaaaaaaaaaaa"}
Returns: "ERROR!"
4)
{"1"}
Returns: "1"
6)
{"..................................................",
"..................................................",
"..................................................",
"..................................................",
"..................................................",
"..................................................",
"..................................................",
"..................................................",
"..................................................",
"..................................................",
"..................................................",
"..................................................",
"..................................................",
"...................................ZZZ............",
"..................................YZZaa...........",
".................................XYY.abb..........",
"................................WXX...bcc.........",
"...............................VWW.....cdd........",
"..............................UVV.......dee.......",
".............................TUU.........eff......",
"............................STT...........fgg.....",
"...........................RSS.............ghh....",
"..........................QRR...............hii...",
".........................PQQ.................ijj..",
"........................OPP...................jkk.",
".......................NOO.....................kk.",
"......................MNN......................kk.",
".....................LMM......................llk.",
"....................KLL......................mml..",
"...................JKK......................nnm...",
"..................IJJ......................oon....",
".................HII......................ppo.....",
"................GHH......................qqp......",
"...............FGG.................rrrrrrrq.......",
"..............EFF..................rrrrrrr........",
".............DEE..................ssrrrrrr........",
"............CDD...................ss..............",
"...........BCC....................ss..............",
"..........ABB.....................ss..............",
".........9AA......................ss..............",
"........899....................tttts..............",
".......788.....................tttt...............",
"......677................uuuuuuuutt...............",
".....566.................uuuuuuuutt...............",
".....550..............vvvvuuuuuuu.................",
"......001......zzzzz..wwvv........................",
".......112.....zzzzz..wwvv........................",
"........223....zzzzz.xxw..........................",
".........3344444zzzzyyx...........................",
"..........444444...yyy............................"}
Returns: "ERROR!"
Largest cycle possible
Submissions are judged against all 97 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TopView with a public method string findOrder(vector<string> grid) · 97 test cases · 2 s / 256 MB per case