Statistics

Problem Statement for "TransformBoardDiv2"

Problem Statement

Lucyanna loves puzzles and she is always eager to invent new ones. She has recently invented a puzzle on a rectangular board.The board is divided into a grid of unit square cells. Each cell is painted either black or white. The rows are numbered starting from 0, from top to bottom. The columns are numbered starting from 0, from left to right.

The puzzle is played in a sequence of steps. In each step Lucyanna must choose exactly two distinct cells. Additionally, those two cells must lie either in the same row or in the same column. Let cell A be the chosen cell that is closer to the top left corner and let cell B be the other one. If both cells currently share the same color, paint cell B white. Otherwise, paint cell B black. After painting cell B using the previous rules, paint cell A white.

You are given the String[] start, the initial coloring of the board. The cell located in row r, column c is black if start[r][c] = '#' and it is white if the corresponding character is '.'. You are also given the String[] target in the same form: the target coloring of the board Lucyanna wants. If Lucyanna cannot get the target board, return the int[] {-1}. Otherwise, return any int[] answer that satisfies all conditions listed below.

  • The int[] answer encodes one possible sequence of steps that solves the puzzle.
  • The length of answer must be the same as the number of steps in your solution.
  • The length of answer must be between 0 and 947, inclusive.
  • If in step i (numbered starting from 0) you chose the cells (r1, c1) and (r2, c2), answer[i] should be equal to (r1 * 1000000 + c1 * 10000 + r2 * 100 + c2).

Definition

Class:
TransformBoardDiv2
Method:
getOperations
Parameters:
String[], String[]
Returns:
int[]
Method signature:
int[] getOperations(String[] start, String[] target)
(be sure your method is public)

Notes

  • Whenever there is a solution, there is a solution that has 947 or fewer steps.
  • Any valid solution will be accepted. It is not necessary to minimize the number of steps.

Constraints

  • N will be between 1 and 4, inclusive.
  • M will be between 1 and 4, inclusive.
  • start will contain exactly N elements.
  • Each element of start will contain exactly M characters.
  • target will contain exactly N elements.
  • Each element of target will contain exactly M characters.
  • No element of start and target will contain characters other than '#' and '.'.

Examples

  1. {"#.",".."}

    {"..",".#"}

    Returns: {1, 10101 }

    The example output describes a solution that consists of two steps. This is it: In the beginning: #. .. Step 0: we choose the cells (0,0) and (0,1). .# .. Step 1: we choose the cells (0,1) and (1,1). .. .#

  2. {"..",".#"}

    {"#.",".."}

    Returns: {-1 }

  3. {"#..#","#..."}

    {"....","...#"}

    Returns: {3, 1000103 }

  4. {"#"}

    {"#"}

    Returns: { }

  5. {"####","####","####","####"}

    {"####","####","####","####"}

    Returns: { }

  6. {"#..#","...#",".##.","####"}

    {"#..#","...#",".##.","###."}

    Returns: {-1 }

  7. {"####","####","####","###."}

    {".###","####","####","####"}

    Returns: {30303, 3 }

  8. {"####","###.","##..","#..."}

    {"...#","..##",".###","####"}

    Returns: {30103, 3, 20202, 10002, 30203, 20003, 1010301, 1000101, 1020302, 1010102, 2030303, 2000203 }

  9. {"#..",".#.","..."}

    {"...","..#","#.."}

    Returns: {200, 1010102 }

  10. {"##.#","####","####","####"}

    {"##.#",".###","####","##.#"}

    Returns: {1020302, 1000102 }

  11. {"###.","####","####","####"}

    {".###","##.#","####","#.##"}

    Returns: {3, 1020302, 3010302 }

  12. {"####","####","####","##.#"}

    {"#.#.","####","##.#","####"}

    Returns: {10003, 2020302 }

  13. {"#.##","####","####","####"}

    {"#.##","#.##","####","####"}

    Returns: {-1 }

  14. {"####","####","####","##.#"}

    {"####","###.",".##.","####"}

    Returns: {2020302, 2000202, 1030203 }

  15. {"#.##","####","#..#","####"}

    {"....","#...","#.##","#..."}

    Returns: {2, 30103, 1010103, 1020202, 1030303, 3010303, 3020303 }

  16. {"#.##",".###","###.","##.#"}

    {"....","#...",".##.","..#."}

    Returns: {100, 20003, 1010102, 1030203, 2000203, 3010302, 3000303 }

  17. {"#.##",".###","#.##","#.##"}

    {"..#.",".#.#","....","#..."}

    Returns: {3, 1020202, 2000202, 2020203, 3020303 }

  18. {".###","##..","####","##.#"}

    {"..##",".###",".#..","...."}

    Returns: {20102, 10002, 1000103, 2000202, 2030303, 3000303, 3010303 }

  19. {"##.#","####","#.##","##.."}

    {"....","....","#...","###."}

    Returns: {1, 30103, 1000103, 1010102, 2020302, 1030203 }

  20. {"##..","###.","####","###."}

    {"####","#...","#...","...."}

    Returns: {-1 }

  21. {"####","..##","####","##.."}

    {".#..","..#.",".###","#..."}

    Returns: {2, 30103, 2010301, 2000201 }

  22. {"##.#","##.#","##.#",".###"}

    {"....",".##.","...#","#..."}

    Returns: {1, 1000102, 30103, 2000300, 2010301, 3020303 }

  23. {".###","####","###.","#.##"}

    {"###.",".#..",".#..","...."}

    Returns: {-1 }

  24. {"####",".#.#","##.#",".###"}

    {"#...","##..","...#","..##"}

    Returns: {-1 }

  25. {"#.#",".#.","###","###"}

    {"#..","..#","#..","#.#"}

    Returns: {1010102, 20202, 2010202, 2020302, 3010302 }

  26. {"#.#","##.",".##","###"}

    {"#..",".##","#..","..#"}

    Returns: {20102, 1000200, 2010202, 3000301 }

  27. {"###","###","###","..."}

    {"...",".#.","..#",".#."}

    Returns: {1, 20102, 1000102, 1020202, 2000202, 2010301 }

  28. {"#.", ".." }

    {"..", ".#" }

    Returns: {1, 10101 }

  29. {"." }

    {"." }

    Returns: { }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: