EllysRollerCoasters

TCO17 Warsaw · 2017-03-31 · by espr1t

TCO17 Warsaw · 2017-03-31 · by espr1t · Greedy, Search

Show categories

Class Name: EllysRollerCoasters

Return Type: String[]

Method Name: getPlan

Arg Types: (vector<string>)

Problem Statement

The test data for this problem contains the backslash character ('\'). Please note that in all examples the backslash characters are "escaped". That is, each backslash is printed as two consecutive backslashes. For example, the string "/-\\" is a string of length 3 that contains a forward slash, a horizontal dash, and a single backslash.

Elly is designing a roller coaster theme park. The roller coasters will be built on a rectangular field. We will use the words "up", "down", "left", and "right" to refer to the four cardinal directions in the field. The field is divided into a grid of square cells. Currently, each cell is either empty or it contains a pylon which will support a rail segment.

Each rail segment will connect exactly two of the four sides of its cell. This means that there are only two basic types of rail segments: straight segments and segments that make a 90-degree turn. A straight segment connects two opposite sides of its cell, and a turning segment connects two adjacent sides.

There are five types of pylons. Each pylon type does only admit two possible rail segments. In particular:

A pylon of type 'S' does only admit a straight rail segment.
A pylon of type 'U' does only admit a segment that makes a 90-degree turn. Additionally, one end of this segment must point up.
Pylons of types 'D', 'L', and 'R' are similar to pylons of type 'U', but this time one end of the segment must point down, left, or right, respectively.

For example, a pylon of type 'U' can either support a segment that connects the upper side and the left side of its cell, or a segment that connects the upper side and the right side of its cell.

Each specific type of a segment will be denoted by a character, as follows:

A horizontal segment will be denoted '-' and a vertical segment will be denoted '|'. (These are the two options for a pylon of type 'S'.)
The character '/' will be used to denote both a segment that connects up and left and a segment that connects down and right.
The character '\' will be used to denote both a segment that connects up and right and a segment that connects down and left.

The investor has several requirements Elly has to satisfy:

Elly must place a railroad segment onto each of the available pylons - no pylon can be left unused. Obviously, the empty cells of the field must remain empty.
Each railroad segment must lie on a cycle, as explained below. There can be arbitrarily many cycles. (If there is more than one cycle, each of them will be used as one roller coaster, so it does not matter.)
The longest cycle will be the "flagship" roller coaster. The longer it is, the more people will come to the theme park, so Elly should try to make it as long as possible.

A railroad segment lies on a cycle if we can start on that segment, follow the railroad in one direction through some other cells, and eventually return back to the starting segment from the other direction without ever getting stuck.

You are given a String[] field: a map of the field. Each character in field will be one of {'.', 'S', 'L', 'U', 'R', 'D'}. Here, '.' represents an empty cell and the other letters represent pylons. If there is no valid way of placing railroad segments onto the given pylons, return an empty String[]. Otherwise, return a String[] that describes one valid placement of railroad segments onto pylons by changing each pylon character into the appropriate segment character: '-', '|', '/', or '\'. If there are multiple solutions, find one that maximizes the length of the longest cycle. If there are still multiple solutions, you may return any of them.

Constraints

field will contain between 1 and 50 elements, inclusive.
Each element of field will contain between 1 and 50 characters, inclusive.
All elements of field will contain the same number of characters.
Each character in field will be from the set {'.', 'S', 'L', 'U', 'R', 'D'}.

Examples

{"RSSLRD",
 "SDDSSS",
 "SULUUS",
 "ULRLDL",
 "RLSSRL",
 "SDUSDL",
 "SRSLRD",
 "RSSSSL"}
Returns: {"/--\\/\\", "|/\\|||", "|\\/\\/|", "\\\\/\\//", "//||\\\\", "|//|//", "|\\-/\\\\", "\\----/" }

Remember that in the strings shown in the example output above each backslash is escaped. The actual plan of the railroad looks as follows: /--\/\ |/\||| |\/\/| \\/\// //||\\ |//|// |\-/\\ \----/ There are three cycles. Their lengths are 34, 10, and 4.

{"RDL",
 "RLL"}
Returns: { }

It is impossible to place the railroad segments onto these pylons in such a way that each segment will lie on a cycle.

{"DSSSSLDSSSDRSSSDDSSDDSSDRDRSSSD",
 "USLRSUSDSSUSDSLSUSDSSDLSSSRSSDS",
 "..SS..SS...SS.SSRSUSSSSSSS...SS",
 "..SS..SS...SS.SSSDSUSSSSSS...SS",
 "..SS..SS...SS.SSSRSDSULSSS...SS",
 "..SS..SS...SS.SSUSSUUSSUUL...UL",
 "..SS..SRSSDSRSLSDSSSSSSSSSSSSSL",
 "..RU..RSSSURSSSURSSSSSSSSSSSSSU"}
Returns: {"/----\\/---\\/---\\/--\\/--\\/\\/---\\", "\\-\\/-/|/--/|/-\\|\\-\\||/\\|||\\--\\|", "..||..||...||.||/-/|||||||...||", "..||..||...||.|||/-/||||||...||", "..||..||...||.|||\\-\\|\\/|||...||", "..||..||...||.||\\--/\\--/\\/...\\/", "..||..|\\--\\|\\-/|/-------------\\", "..\\/..\\---/\\---/\\-------------/" }

If printed without the escape backslashes the only valid output looks like TCO2017.

{"DD.RSSSL.....DSSLRL.DSSLRL..RLDSD.DSSSSSSD",
 "SUSU...UDDSSLRSSLSS.UL.RUUSSURU.UDS.DSD.DU",
 "SRSL.RSSLUL.RDRD.RU..USD.RSSSLRSLSUSLRU.S.",
 "SS.RSU.DDRL..SSSDLDSSSDRDRL.RUS.RU.RDULRL.",
 "SRSDRSSUSS.DSURURLRD..UDULRSU.S.RSSLSRLRD.",
 "SRLSUD..UL.RLDSDDL.RD..SRLRL..S.S.DSUS..RD",
 "SSSS.S.RSSLDURLSUUDLUL.UU.RUDSL.SDU..S.RLS",
 "RUSS.S.S.DLSDDRL..RU.UD..RSSU.DLULRD.ULULS",
 "DSLS.RDRSLRLUURLRL.RDRLRDSDD..RURSURL.S..S",
 "S.RLRLUD.RURL.RURU.SUUDLSSUU.DD.S.DSL.USSL",
 "RSU.SS.S.S.RU.DSD..RL.RDSUSSSLRSU.S.DLDL..",
 "DSSSLRSL.S..DSU.RDDLRDDLS....RD...USLUURSD",
 "RLDSSSLRSUDDS.DSDSSSRLRDUSSLDLUSSSSL.DL..S",
 ".SSDDDUS..SSS.RDSULSRSLS.DDSRSDDLRLRDSUSSL",
 ".RURLUDSRLRLRSDUURLRSLSS.RLRL.SRLRU.UL.DSL",
 "RSSL.RUSSSRD..RSDRU.DLSS..RDULS.DSSDDL.USU",
 "SDLRSL.UUSSSRD.DUDDDU.RU.RUUDULRUDDRLS.RSL",
 "ULSDSSLRSURLRU.SRUUURSSSSL..S..S.SSRSU.ULS",
 ".RURDRUUL..RSDDLS..RUDSSSSL.RD.S.RUUSDRDSS",
 ".RSSUS..UL.S.RU.RL.UDRSSSSLDLUSUDSSSSLRUUU",
 "RL..RLRSLS.RSD.RSURDRSSSDDSUUSSSLRSSDDL.RD",
 "SRSLSRLRLSDL.S.RL.RLRLDSUUD..RL..RSSLSS.UU",
 "RSLULUSLRLRL.SDLSRSSUSUSSSU.DUS.DSD.RURL..",
 ".RLDSDRLRSLRDSUUSUL..RSSSSSSL.UDUDRLRSDUSL",
 ".RSU.SULRSUSSS.DL.S.DSSSD.RL..RL.SDUDDULDL",
 "RSSLRURDRD.RUSRUDLRSL.RDULUURSU.DUS.UL.SS.",
 "USSUSDUS.S.RDSRDSUD.RDUL.SRLS...SRLDD..SUL",
 ".RSSURLS.RLSSRSUUSL.SS...SULRL..RUDLSDLS.S",
 ".SDDDSUS.DLUU..DD..RURSSSUDSSURSSLRSUSULRU",
 ".SSSRSDRDS.RSD.UURLSRD.DSLRLRLS.RU.DSU.RL.",
 "RUSRSSLDURLULUL..SSSSUSL.S.SUUUSLRDUSL.SDD",
 "RSL..RLRD.UDS.S.RLRLUD.DDS.S.RSSSLUD.USURL",
 "DSSSDUL.S..SRDSDU....SDLRL.SDL..DSDUSSSSSL",
 "UDDSU.RDRSDSRUSRSD.DLSS.DL.ULRSLS.RLRSD.DL",
 ".UU.RLULDLRURSUDLS.RLUL.SS...SDURL.RLDU.S.",
 "RDDDSSDDSUSLDSLSSS...RSSLUSDDUS..S.DDRD.RL",
 "RUUURLULUSSLRSLUUUSSSL.....UL.USSL.UL.USSU"}
Returns: {"/\\./---\\...../--\\/\\./--\\/\\../\\/-\\./------\\", "|\\-/...\\\\/--\\\\--/||.\\\\.\\/\\--/\\/.\\\\|./-\\.//", "|/-\\./--/\\\\.\\\\/\\.\\/..\\-\\./---\\/-\\|\\-///.|.", "||.\\-/./\\//..|||/\\/---\\\\\\\\\\.//|.\\/./\\\\\\//.", "|\\-\\/--/||./-/\\/\\/\\\\..\\\\\\\\\\-/.|./--/|//\\\\.", "|/\\|\\\\..\\/.\\\\/-\\/\\.\\\\..|///\\..|.|./-/|..\\\\", "||||.|./--\\//\\\\|\\//\\\\\\.\\/.\\//-/.|//..|./\\|", "\\/||.|.|.//|/\\\\/..\\/.\\\\../--/./\\\\//\\.\\\\\\/|", "/-/|.\\\\\\-///\\//\\/\\./\\///\\|/\\..\\//-/\\\\.|..|", "|.///\\\\\\.///\\.\\/\\/.|\\///||\\/./\\.|./-/.\\--/", "\\-/.||.|.|.\\/./-\\..\\\\.\\\\|\\---/\\-/.|./\\/\\..", "/---/\\-/.|../-/.\\\\/\\\\\\//|..../\\...\\-/\\/\\-\\", "\\\\/---\\/-//\\|./-\\|||//\\\\\\--\\//\\----\\./\\..|", ".||/\\//|..|||.\\\\|\\/|\\-\\|./\\|\\-\\/\\/\\\\\\|\\--/", ".\\/\\/\\\\|/\\\\/\\-\\\\//\\\\-\\||.\\/\\\\.|\\/\\/.\\/./-\\", "/--\\.//|||/\\..\\-\\\\/.//||../\\\\\\|./--\\/\\.\\-/", "|/\\\\-/.\\/|||/\\.///\\//.\\/.//\\\\\\////\\\\/|./-\\", "\\/|/--\\/-/\\/\\/.|//\\//----/..|..|.||/-/.\\\\|", ".//\\\\//\\\\../-\\//|..///----\\.\\\\.|.\\/\\-\\/\\||", ".\\--/|..\\\\.|.\\/.\\\\.\\\\\\----//\\\\-//----/\\/\\/", "/\\..///-\\|.\\-\\./-//\\\\---\\/-/\\---//--\\/\\./\\", "|\\-\\|////|/\\.|.\\\\.\\//\\/-/\\\\../\\..\\--/||.\\/", "\\-\\\\/\\-///\\/.|/\\|/--/|\\---/.//|./-\\.//\\\\..", ".///-\\/\\\\-\\/\\|\\/|\\\\..\\------/.\\\\\\\\\\\\\\-\\\\-\\", ".\\-/.|\\//-/|||.//.|./---\\./\\..//.|///\\\\\\//", "/--\\///\\\\\\.\\/|///\\\\-/./\\\\\\\\//-/.//|.\\/.||.", "\\--/|//|.|./\\|\\\\|\\\\./\\\\/.|/\\|...|///\\..|\\\\", "./--/\\\\|.\\\\||\\-/\\-/.||...|\\/\\\\..\\///|/\\|.|", ".|/\\/-/|.//\\/../\\..//\\---//--//--\\\\-/|\\///", ".|||\\-\\\\\\|./-\\.\\//\\|/\\./-\\\\\\/\\|.//./-/.//.", "//|\\--///\\\\\\\\\\\\..||||\\-/.|.|\\/\\-//\\\\-\\.|/\\", "\\-/../\\\\\\.\\\\|.|.//\\/\\\\./\\|.|./---/\\\\.\\-/\\/", "/---\\\\/.|..|\\\\|//....|//\\/.|//../-\\\\-----\\", "\\\\/-/./\\\\-\\|//|\\-\\./\\||./\\.\\//-\\|.\\\\/-\\.//", ".\\/./\\\\//\\\\/\\-//\\|.\\/\\/.||...|//\\\\.\\///.|.", "/\\/\\||/\\|\\-\\/-\\|||.../--/\\-\\//|..|./\\\\\\.\\\\", "\\/\\/\\/\\/\\--/\\-/\\/\\---/.....\\/.\\--/.\\/.\\--/" }

{"RLRSSSSSDSDSSSSSSSSL.DLDLDLSDLRDURSDUUDSSSSSSD.RD", "SRU.LRLSUSU.DSSD.DLRLRLUUUUSRLUUDLSUSSLDSSSSDSLUL", "RLRSSLUSSSSSURDULUU.USL.LDSSLDDRLRSSDDDSRL..SSDDD", ".SSRSSLRLRDDDSULUSSL..SSRL..SSUUSRDDUUURUUSSLRLUL", ".RURSSURLRLUURSU.LRUSSL.RSSSLUSSSSUUSSSSSSSSSSUS."}
Returns: { }

Submissions are judged against all 86 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class EllysRollerCoasters with a public method vector<string> getPlan(vector<string> field) · 86 test cases · 2 s / 256 MB per case