Connection Status:
Competition Arena > BoardCoveringDiv2

BoardCoveringDiv2

TCO19 SRM 741 · 2018-10-30 · by Blue.Mary

TCO19 SRM 741 · 2018-10-30 · by Blue.Mary · Simple Search, Iteration
Class Name: BoardCoveringDiv2
Return Type: String[]
Method Name: make
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Lucyanna loves puzzles and she is always eager to invent new ones. She has recently invented a puzzle based on placing trominoes onto a square board.

The board is divided into a grid of unit squares. One of the unit squares on the board is black, all others are white.

A tromino is any connected piece that exactly covers three unit squares of the board. (Trominoes come in two shapes: "L" and "I".)

The goal of the puzzle is to cover all white squares of the board using trominoes. More precisely, the rules for Lucyanna's puzzle are as follows:

  • The player must place some trominoes onto the board.
  • Each tromino must exactly cover three unit squares of the board. (Thus, each tromino must lie completely inside the board.)
  • Each white unit square must be covered by exactly one tromino. (Thus, the trominoes cannot overlap.)
  • The black square must remain uncovered.

You are given the String[] board that encodes a valid solution to one of Lucyanna's puzzles. In the solution, Lucyanna used 52 "colors" to color the trominoes, while making sure that adjacent trominoes always have different colors. (Trominoes are adjacent if they share a side of a unit square.) The "colors" used are all uppercase and lowercase English letters ('A'-'Z' and 'a'-'z'). Additionally, the character '#' represents the uncovered black square.

Lucyanna would like to present the same solution but now she wants to use only 10 "colors": the characters '0'-'9'. Recolor all pieces of board using these new colors and return the resulting String[]. (Obviously, the new coloring must still follow the rule that adjacent trominoes must have different colors. You can only re-color the given trominoes, you cannot change their arrangement.)

Notes

  • There are always many valid solutions. You may return any one of them.

Constraints

  • N will be between 1 and 47, inclusive.
  • board will contain exactly N elements.
  • Each element of board will contain exactly N characters.
  • Exactly one character in board will be '#'.
  • All other characters in board will be uppercase and lowercase English letters ('A'-'Z' and 'a'-'z').
  • When board is viewed as a two-dimensional grid of letters, each connected group of equal letters will consist of exactly three letters.
Examples
0)
{"#a",
 "aa"}
Returns: {"#0", "00" }

This is a 2x2 board with a single tromino. In the input, this tromino has the color 'a'. In the sample output we changed the color to '0'. We could have used any other color ('1'-'9').

1)
{"AAAE",
 "BBBE",
 "CCCE",
 "DDD#"}
Returns: {"0001", "2221", "0001", "111#" }

A 4x4 board with five trominoes. The returned board with new colors looks as follows: {"0001", "2221", "0001", "111#" } Note that trominoes may share the same color as long as they are not adjacent.

2)
{"ABCCC",
 "ABAAA",
 "AB#EF",
 "GGGEF",
 "HHHEF"}
Returns: {"01000", "01222", "01#01", "22201", "11101" }

The solution given in board may also contain multiple trominoes that share the same color. This particular solution contains two trominoes that have color 'A'. Note that in your solution you may use different colors for such trominoes. E.g., the example output changes one of the 'A' trominoes to '0' and the other to '2'.

3)
{"AAAOHHH","BBBOIII","CCCOJJJ","DDD#KKK","EEEPLLL","FFFPMMM","GGGPNNN"}
Returns: {"0001000", "2221222", "0001000", "111#111", "0001000", "2221222", "0001000" }
4)
{"AAAnAAAnAAAnAAAnAAAnAAAnAAAnAAAnAAAnAAAn","BBBnBBBnBBBnBBBnBBBnBBBnBBBnBBBnBBBnBBBn","CCCnCCCnCCCnCCCnCCCnCCCnCCCnCCCnCCCnCCCn","DDDoDDDoDDDoDDDoDDDoDDDoDDDoDDDoDDDoDDDo","EEEoEEEoEEEoEEEoEEEoEEEoEEEoEEEoEEEoEEEo","FFFoFFFoFFFoFFFoFFFoFFFoFFFoFFFoFFFoFFFo","GGGpGGGpGGGpGGGpGGGpGGGpGGGpGGGpGGGpGGGp","HHHpHHHpHHHpHHHpHHHpHHHpHHHpHHHpHHHpHHHp","IIIpIIIpIIIpIIIpIIIpIIIpIIIpIIIpIIIpIIIp","JJJqJJJqJJJqJJJqJJJqJJJqJJJqJJJqJJJqJJJq","KKKqKKKqKKKqKKKqKKKqKKKqKKKqKKKqKKKqKKKq","LLLqLLLqLLLqLLLqLLLqLLLqLLLqLLLqLLLqLLLq","MMMrMMMrMMMrMMMrMMMrMMMrMMMrMMMrMMMrMMMr","NNNrNNNrNNNrNNNrNNNrNNNrNNNrNNNrNNNrNNNr","OOOrOOOrOOOrOOOrOOOrOOOrOOOrOOOrOOOrOOOr","PPPsPPPsPPPsPPPsPPPsPPPsPPPsPPPsPPPsPPPs","QQQsQQQsQQQsQQQsQQQsQQQsQQQsQQQsQQQsQQQs","RRRsRRRsRRRsRRRsRRRsRRRsRRRsRRRsRRRsRRRs","SSStSSStSSStSSStSSStSSStSSStSSStSSStSSSt","TTTtTTTtTTTtTTTtTTTtTTTtTTTtTTTtTTTtTTTt","UUUtUUUtUUUtUUUtUUUtUUUtUUUtUUUtUUUtUUUt","VVVuVVVuVVVuVVVuVVVuVVVuVVVuVVVuVVVuVVVu","WWWuWWWuWWWuWWWuWWWuWWWuWWWuWWWuWWWuWWWu","XXXuXXXuXXXuXXXuXXXuXXXuXXXuXXXuXXXuXXXu","YYYvYYYvYYYvYYYvYYYvYYYvYYYvYYYvYYYvYYYv","ZZZvZZZvZZZvZZZvZZZvZZZvZZZvZZZvZZZvZZZv","aaavaaavaaavaaavaaavaaavaaavaaavaaavaaav","bbbwbbbwbbbwbbbwbbbwbbbwbbbwbbbwbbbwbbbw","cccwcccwcccwcccwcccwcccwcccwcccwcccwcccw","dddwdddwdddwdddwdddwdddwdddwdddwdddwdddw","eeexeeexeeexeeexeeexeeexeeexeeexeeexeeex","fffxfffxfffxfffxfffxfffxfffxfffxfffxfffx","gggxgggxgggxgggxgggxgggxgggxgggxgggxgggx","hhhyhhhyhhhyhhhyhhhyhhhyhhhyhhhyhhhyhhhy","iiiyiiiyiiiyiiiyiiiyiiiyiiiyiiiyiiiyiiiy","jjjyjjjyjjjyjjjyjjjyjjjyjjjyjjjyjjjyjjjy","kkkzkkkzkkkzkkkzkkkzkkkzkkkzkkkzkkkzkkkz","lllzlllzlllzlllzlllzlllzlllzlllzlllzlllz","mmmzmmmzmmmzmmmzmmmzmmmzmmmzmmmzmmmzmmmz","AAABBBCCCDDDEEEFFFGGGHHHIIIJJJKKKLLLMMM#"}
Returns: {"0001000100010001000100010001000100010001", "2221222122212221222122212221222122212221", "0001000100010001000100010001000100010001", "1110111011101110111011101110111011101110", "2220222022202220222022202220222022202220", "1110111011101110111011101110111011101110", "0001000100010001000100010001000100010001", "2221222122212221222122212221222122212221", "0001000100010001000100010001000100010001", "1110111011101110111011101110111011101110", "2220222022202220222022202220222022202220", "1110111011101110111011101110111011101110", "0001000100010001000100010001000100010001", "2221222122212221222122212221222122212221", "0001000100010001000100010001000100010001", "1110111011101110111011101110111011101110", "2220222022202220222022202220222022202220", "1110111011101110111011101110111011101110", "0001000100010001000100010001000100010001", "2221222122212221222122212221222122212221", "0001000100010001000100010001000100010001", "1110111011101110111011101110111011101110", "2220222022202220222022202220222022202220", "1110111011101110111011101110111011101110", "0001000100010001000100010001000100010001", "2221222122212221222122212221222122212221", "0001000100010001000100010001000100010001", "1110111011101110111011101110111011101110", "2220222022202220222022202220222022202220", "1110111011101110111011101110111011101110", "0001000100010001000100010001000100010001", "2221222122212221222122212221222122212221", "0001000100010001000100010001000100010001", "1110111011101110111011101110111011101110", "2220222022202220222022202220222022202220", "1110111011101110111011101110111011101110", "0001000100010001000100010001000100010001", "2221222122212221222122212221222122212221", "0001000100010001000100010001000100010001", "111222333222111222333222111222333222111#" }

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

Coding Area

Language: C++17 · define a public class BoardCoveringDiv2 with a public method vector<string> make(vector<string> board) · 19 test cases · 2 s / 256 MB per case

Submitting as anonymous