Problem Statement |
| | You are given a maze. Each cell of the maze contains a wall, an empty cell or a ball of some color.
You are given the starting configuration of the maze. You want to move the balls into another, target configuration. To do this, you can roll balls, one at a time, in straight lines (horizontal or vertical). Once the ball starts rolling, it stops only when it hits a wall or another ball (which does NOT start moving). Balls can't roll out of the maze, so they stop when they hit a border of the maze. Each rolls starts only after the previously rolling ball has stopped, so at any time there is at most one rolling ball in the maze.
You have to do at most 20 * (number of balls in the maze) rolls. After all balls stop moving, their configuration must be as close to the target one as possible.
Implementation Details
Your code should implement one method restorePattern(String[] start, String[] target).
start and target give the starting and the target configurations of the maze, formatted as follows: character j of element i represents cell in row i and column j. '#' is a wall, '.' is an empty cell, '0'..'9' are balls of various colors. Walls are located in the same cells in start and target, the only difference is in the positions of the balls. The set of balls' colors will also be the same.
Your return from this method should be a String[], containing at most 20 * (number of balls in the maze) elements. Each element of your return should be formatted as "R C D", where R and C are row and column coordinates of the ball you want to roll, and D is the direction of roll: 0 decreases column, 1 increases row, 2 increases column and 3 decreases row. (See visualizer for implementation of roll directions.)
Scoring
Your score for a test case will be calculated as follows. For each ball in target configuration you get 1 point if the end configuration has a ball of the same color in this cell, or else 0.5 points if it has a ball of different color in this cell. The score is the sum of points for each ball in target congifuration, divided by the total number of balls in the maze. If your return contains an invalid roll or too many rolls, your score for this test case will be 0. Your overall score will be a sum of your scores for individual test cases.
Test Case Generation
-
Width and height of the maze are chosen between 10 and 60, inclusive.
-
The number of colors is chosen between 1 and 10, inclusive.
-
Walls density is chosen between 10% and 30%.
-
Balls density in empty cells is chosen between 5% and 20%.
-
Each color is selected with equal probability.
-
Target configuration is generated as follows: each cell is generated independently, containing a wall, a ball of some color or an empty space.
-
To get start configuration, random balls are rolled in random directions until they hit a wall, a border of the maze or another ball.
Tools
An offline tester/visualizer is available here.
You can use it to test/debug your solution locally.
You can also check its source code for exact implementation of test case generation and score calculation.
|
| |
Definition |
| | | Class: | RollingBalls | | Method: | restorePattern | | Parameters: | String[], String[] | | Returns: | String[] | | Method signature: | String[] restorePattern(String[] start, String[] target) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The time limit is 10 seconds and memory limit 1024MB. |
| |
Examples |
| 0) | |
| | | Returns:
"seed = 1
W = 10, H = 10
Balls in maze = 5
Start maze:
#00......#
...##...#.
....#...#.
..........
#.#...#0..
..#......#
.0#.....#.
.#.0..##..
#..#....#.
#....#....
Target maze:
#........#
...##...#.
.0..#0..#.
.00.......
#.#...#...
..#......#
..#.0...#.
.#....##..
#..#....#.
#....#....
" | |
|
| 1) | |
| | | Returns:
"seed = 2
W = 20, H = 20
Balls in maze = 44
Start maze:
.#.#.0#.#0..#...1##.
.1#.#.10.........##.
........1#.....#....
0.......1#..........
#.......##.....#0...
#..1...0....0..1#1..
.1.#...#1.........#0
.1....1......1....00
..#...#......#...0.0
0......#.1#..1...#..
1#.......#..........
....#.#...#.0.....#.
.#..#....#..#.....#.
....#..##1#.#...#..1
.........0##....#...
..........0...#...#.
.........#.........#
....#......#.......#
0...#1...#..1.......
#.0#......11#0.#10.0
Target maze:
.#.#..#.#...#1...##.
1.#.#...0.0..1...##.
......10.#.....#....
.11......#..1.0.....
#00...1.##.....#....
#......1........#..0
..1#..0#.1..0.....#.
..0.....0...........
..#..1#..1.00#......
..1....#..#......#..
.#...0...#..........
....#.#...#....0..#.
1#..#....#..#.....#0
1...#..##.#0#...#...
..........##1...#...
.........1....#...#1
..0....01#...1.....#
....#...1..#.......#
..00#....#........1.
#..#........#..#....
" | |
|
| 2) | |
| | | Returns:
"seed = 3
W = 30, H = 30
Balls in maze = 110
Start maze:
0001..1.#...#........0.112....
.....2.0....#.##.1##.2#.#.....
........#2#2.2#..0#01........0
.........01.22....#........0#.
..#.#...0.2...#..#...........#
....1#.......#...#.....2.....0
..#.#2.#0..............1.....2
..#2.1...#..##...#....##.....0
..111................002##....
.#.....#2..............1.....1
........#..........#.#010#..#1
...#22...0#.....#.##1.#.#...#.
#...#.....2.....1.02..........
1#2.1.........1.....#.....#...
..............#...#1#....##21.
........#2.......#........2#..
....0#1.2.....0#..............
1.....20................#....2
.1#...0..#....#...2..........1
1.............................
2.#...................#......1
.......#.......#...#..#..#1...
.....#............##...#..0..1
.#...02.........#...........#.
......#..#......1.0#..#....#..
#.....#...........20.2........
0..1##...#.#0..#....##.....#..
...#.2......##...2.......#....
2...01..#.....#..0.#..#.....0#
20..2#2......##1....##.0#..0.1
Target maze:
2..0.1..#2..#2.......2........
............#.##1.##..#0#2....
........#.#0..#01.#.........2.
....0.0........2..#......10.#.
0.#.#.....00..#..#...........#
..2..#.12....#...#0.11....00..
.1#.#..#.............0...1..1.
..#......#..##...#..2.##......
.1........0.11......0.21##1...
.#..2..#............2.0.......
.1.2....#..........#.#...#..#.
...#..0..2#2..0.#.##..#.#...#2
#..1#.2..............011...21.
.#..................#.....#...
...11.2.......#...#.#...1##..1
........#........#.2.1...1.#..
.....#....2....#...........20.
......12......1.110.....#.....
..#..2..0#2..2#.2...2.........
......0...........1.0.........
..#.2.......0.........#.......
.......#0......#...#..#..#....
.1...#............##.0.#.....0
.#.......1......#.......1...#.
.....2#..#......2..#..#....#..
#.1...#.......................
.00.##2..#.#...#2...##...0.#..
..0#.....1..##...........#....
...2..2.#.....#.0.0#..#......#
2....#.......##.1...##..#.0...
" | |
|
| 3) | |
| | | Returns:
"seed = 4
W = 46, H = 34
Balls in maze = 177
Start maze:
#............0....#...##..43...2...9..01#.4..9
..#..#............#.#...##..........#...#.....
..#.#...#......#......................50..7#.#
.....#................#.##24##........#.7...#.
...##....#...............3.#...........7..84..
...#.##..7.13.#7...#4......#3.....9#7..#.5#..#
......7##..#54....#.5#5......##...17.....9.##.
1...#......1#...6#3.........#.#...#.#.........
#...#...##....2933.........50.4#.............#
.5.....##.#.....#..#......#3..014.............
0.........3....#19....#....#.#.#.....52.....5.
.#...#..##1....#..#1##8.#7..2.67.....#......#.
9.............8#...4##3.....#6..........#..#.0
#......###.....1#.....29.....#7.4............8
.....#.....#.9#7........#....3..#.#8......2...
........#....6##.....#...#2................3..
..5.#0.70......2#...#..0#.2#.............#.#..
.#..##5###...#961..65..54..1..........#..###..
5..#45#7.......#.#.#0.......#................9
6##.6##.4....#7#.........#07.................0
...#.#.6##..###..#......5......8#4....#.....#4
..16.........0.9.####.....................#...
.....#......#6.#..6....#....#..#.#.#..#..9...6
3.#.#..#......837....789.#........#9...4.#.0..
#5.......#...#..#..#..#1.##00........#.3.21#.#
.##......#18.....9#1.......##....##.......1.6#
..#....#.....#.............#2.........4#...#.7
..4#.......#.88#..#......#...........#.....#..
..........132.#....4#.#..#2....#......#...6...
.#........#...#......#.......#.........3#..#.2
#...#...............................#.....#.1.
67#................................8..#.......
.........#...1#..........#6.........#...#.....
.#.......#....#.5..........9.#.##.42..1....9#.
Target maze:
#..7....8.......0.#4..##....42.3........#.....
.6#..#..1...7.....#.#.7.##...9..6..3#4..#..5.9
..#.#...#14....#.2...8...............2.7...#.#
..5..#..........9.....#.##..##....9.9.#.....#4
...##....#.................#.1......7.1..7....
.3.#.##.......#..7.#..8....#5....7.#...#..#..#
7......##..#....3.#..#.......##...........5##.
..9.#.......#....#..........#.#...#.#0.7....0.
#...#...##35.....0..........4..#.0...........#
.......##.#.....#..#......#.5......2.627......
...........5...#......#.7.2#.#.#............2.
1#...#..##.0...#..#.##..#............#.0....#.
...0.0........2#41.3##89..3.#....5......#..#.9
#9...45###......#7...........#.......963..8...
...0.#.....#..#.........#.......#.#.....1...4.
........#.....##53.4.#9..#1.........8.........
...5#...........#...#...#..#...........9.#.#..
.#..##.###353#....4.6....8......1.2...#..###..
7.5#..#.1......#.#.#.....3..#.5.......4.......
1##..##..1...#.#..9......#..3...637.......2...
...#.#..##.7###..#...0..........#.....#..4..#.
.................####..9.7....2......6....#0..
06.5.#......#.9#.......#....#9.#.#.#..#.5.....
..#.#..#..........7......#0......0#...3..#....
#.6.4...6#...#..#..#..#.1##....0...9.#.....#4#
.##....2.#.......3#........##8.6.##0.7...2...#
..#.91.#.....#........8...4#.........1.#...#..
84.#.....8.#...#..#......#.8.........#3....#.1
........6..1..#.....#.#..#.....#......#.......
.#........#...#......#.5.....#...4......#..#..
#...#.7....11.......................#....2#...
..#......66..1...........6............#.......
.........#....#..........#..........#..2#.....
.#.......#...2#1.1..4...5....#.##4.......6..#6
" | |
|
| 4) | |
| | | Returns:
"seed = 5
W = 43, H = 45
Balls in maze = 247
Start maze:
...#.1..0#.#0....110...#1..0#.#.#1..1...#.#
........11..........#.#...1.0#...#.#.#.....
.....0#1#01#.#.#.##...#.1#..1............0#
.#.......1#.......0101.#...0#1...........##
0......#.#0#.#0........#........#.#...0.#.1
1#....0....#.#.#.##...0.........01....###..
#..#.0...#....#.....#.#..##...0..##..1.....
11....#........#..#1.#1.#....1......#..##..
0#.#.#.0#.##..0..#....0##.#.##..#.##......#
....0#.#.1...01...0##.#..##.....0.1.####1..
...0#.0#.#0.##....0....0#..##.......#1...#.
..1..#....01#..##...#........#........#..0.
..##0#.#....#.......#........#...#.0.......
.##.#...1...#....#........1#.#..#..###.....
.##.1...#..#1............#11....0...0#....0
.1...#.1.....#.##.#..0#...#.#..#........11#
.0.....1#....1..##.#.#0#.#...11...###1.....
...0.1###...#........1#......##..0.00..#...
..##.11.....#..#....11#1..##..#...#0.....1.
#.#1..#.1.#.....#..##...0#.#10............0
.0....#....#......#.##.......##0..1........
##.................10#.#.#...#0.##....#1...
.0........#.#...##...#0...##.0.###.#.#0....
.#.##....#.##...#........0100.....0#...1#.#
0#......1.##10....#......1#.1...#..##..#.#0
1...#0..0.#0#...........0.#.....#1.0#..##.1
..#1...0..#...............1..#.#.1#.#..1#..
.00....#.01.........1..#....0#....#...#.#..
.......#........1#..##.#0.0##...#.#..#....1
....#..#01.....1#1.#.#.1#..#...10.#......0.
.#......1#....#0..0#..#.1...0#..#...#...#..
.#..##.0...11...#..........###1.11#........
####..01....#..0#.#...........0#.........#.
##....#...#10.00...........###1.0#.......00
0..##...10.1.##...#...#...#..#.#.....#..#.#
11...11.##..#..0##...#.......1##.#..00#.1#.
.....1#..#......1..#.#.#.........#01..#....
.#..#.......1#....#.#1.....#1#.1..1##0.....
.#..#......##1.....1.#.#.#.##.1#.##1#......
...........##.....##.###........#...#..#..#
0.....#.....#...0##......#.00#........1..##
..0#..#.#....#0####.#.....#.#.........11..0
0.0..........#0...01....1.....1#..#....1#..
...##.#1......#..#0..#..1#.0#.....0#...#..#
.#.1##.1..#1.......###1##..#01.#.0.1##....0
Target maze:
...#.0...#.#.........1.#.1..#.#.#.......#.#
..1....1..1......11.#.#1...0.#...#.#.#...0.
0..1..#.#..#.#.#.##..0#1.#1...0.1.........#
.#0...1.0.#.1...01.0...#....#.......1....##
1....0.#.#.#.#....00...#....1..0#.#..1..#1.
.#..00.....#.#.#.##....1..1....1......###..
#1.#.....#....#.....#0#0.##.....0##........
...0..#...0....#..#..#..#.......1...#..##..
.#.#0#..#.##.01..#....1##.#.##..#.##......#
....1#.#...1.......##.#..##0........####...
....#0.#.#.0##...0......#..##...1..0#0...#.
1....#01....#..##...#0....0..#1.......#....
..##.#.#....#.......#........#..0#......0..
.##.#0......#....#.....0...#.#..#..###.....
.##.....#.1#..1...1......#.....100...#...1.
1.0..#....01.#.##.#011#...#.#..#..........#
.....0..#..0....##.#.#0#1#.......1###.0.0.1
......###...#.1.0.....#......##..1....0#...
.0##...10...#..#......#...##..#0..#...11...
#1#...#0.1#10...#1.##....#.#...1....0...1..
1.....#....#....1.#.##.......##.0...0......
##11.............0...#.#.#.0.#..##1.0.#....
0.........#.#...##...#1...##...###.#.#.1...
.#.##...1#.##.1.#.0.0...........11.#....#.#
.#.......1##.....0#.0.....#.....#..##..#.#.
..1.#.....#.#100....1..0..#...0.#...#..##0.
..#.11.1..#.1..1.............#.#1.#.#...#..
0..0...#...1........0..#.0...#...1#.0.#.#..
.......#0........#..##1#..1##...#0#..#..11.
....#..#......0.#..#.#..#..#..0..0#........
.#....000#....#.0..#..#....0.#..#..1#...#.0
.#..##0.1.......#10........###0...#..0..0..
####1...1...#.01#1#....1....0..#...1.....#.
##....#.0.#...1..0.........###...#.1.0.....
..0##0....1..##...#...#...#.1#1#.01..#..#.#
........##.1#.0.##...#........##1#....#..#.
01....#..#...10.0..#.#.#.1......0#....#....
.#..#0.......#.0..#1#..1.11#.#.....##......
.#.0#......##........#.#.#0##1.#.##.#...0..
....1.....1##1....##.###1..01.1.#1..#.1#.1#
......#.....#..0.##00....#0..#...........##
...#.1#.#.1..#.####.#1....#.#.01..00.....1.
.............#........1........#1.#1..1.#..
1.1##.#......1#..#..0#...#..#......#...#..#
.#..##....#........###.##..#...#....##..0..
" | |
|
| 5) | |
| | | Returns:
"seed = 6
W = 25, H = 52
Balls in maze = 118
Start maze:
.##2..1.#..#2..#........1
22...#.....2.2#.10.##..#.
0...1...........#.#....#.
......#..........##.#....
#..........#....#......1.
.........#.........#....0
1..........#...1.......#1
#..#......1.#0..#....#..#
.....#..#0...#...........
#.1.....#2.##....2#.##..#
..#.....#.......#.......2
..#.##..#.2...#...0#.....
#.#.....0..1#............
.#...#...1#.0...1.#......
....02#1....2###1.1#.#...
.....#...#......###.#....
..............##...#.0#.2
.###................20#1.
.....0.#...#.........#.#1
....##.....0....1#.#..#..
02......#...#..#2.......1
....#.#...#.....#1.......
..#...........#.........0
...#....#...#.....#......
.#.#...#0...............#
...##..........#..#....0#
.1#....00#..221#.......##
..........1.#0..0....#...
2#...........0#.#.##.....
1..................#.....
##............#.....#..#.
.0.......0#..#0.....1#.#.
......#.#..........#.1...
....................#...#
1............#......#1...
.............1.#...#.....
....#...#2..1....0.2.....
2.1......##.2...##...#.#.
#02.......#1#1.........#.
#.....###2.2..........#..
.#...2.0#.2#..0..........
0...##...#.##.###...1....
..#.....#...........##...
................#.##.....
..............##1........
....#.....#.......#....#.
.1###........1#1..1.....1
02...##.......#..###..#0.
#..10.#..................
2#......#.#1...#....##...
1............01#......11.
22...1..1.1#1..0.#....#..
Target maze:
.##0....#..#...#.1....0..
....1#1.......#....##..#.
....2...11...1..#.#....#.
......#0...1.2...##.#....
#....1.....#....#...1....
......1..#........1#.1.0.
..........1#...........#.
#..#..0.....#.2.#..2.#..#
.....#..#...2#..2.....0..
#2......#..##...1.#.##..#
..#.....#.2.....#........
..#.##20#...2.#.2..#.....
#.#........0#............
.#...#....#.......#......
..0.1.#......###...#.#..2
.....#...#...0..###.#....
.....2...1...2##...#..#..
.###...0....1.1.......#..
.......#...#.......1.#.#.
....##...........#.#..#..
........#...#..#.0.......
....#.#..2#.....#.......1
..#...........#..........
...#....#...#.....#......
.#.#...#...........0...0#
...##..0.......#.0#.01..#
..#......#.....#.0.....##
...1........#..1.....#...
.#2...1.......#.#.##...1.
......0.22..1....1.#.....
##1.2.........#.....#..#.
.......21.#..#.0.....#.#.
...0..#.#........1.#.....
...........1......0.#...#
.....1.....00#2...1.#....
.1.............#...#.....
....#...#................
......0.0##.....##10.#.#.
#.........#.#..........#1
#.....###.....0....1..#.2
.#2.....#2.#.............
..20##...#.##.###........
..#.....#1........2.##.1.
1....11.0.......#.##..1..
..0.......1...##...1.0..0
....#.....#.......#...1#.
..###.........#..........
20.0.##.......#..###..#..
#.....#.......1..........
.#.2.12.#.#..2.#....##...
............1..#.2..11...
..2........#.....#....#..
" | |
|
| 6) | |
| | | Returns:
"seed = 7
W = 57, H = 52
Balls in maze = 306
Start maze:
1....1...###10.....##0#.#1.#...###.....#.#....#..0....#1.
#.1#.....#...#..#.1......##...0..0.###1.....#1.0.11#..#..
.#..#......##1.##..#.........##.#.0#1..1#.1###.#....#....
1.............#..1.##...#.#.....#.#...#.#.#1#.......0#...
..#.1...00#.1....0##..#..#.#..####0.......#..#......#...1
..#...###..1...1#0#..#...#..#.0..#.#...........#...#....#
.#1...##..##....##...#...#011..##1.1.##...#..#..#0...#...
1......1....#...1......1.#.......#.....##...#0....#......
1.....#0.....###..####.#1....#.....#.##.#0...#...#......0
#..##.0....#.##..##1..0.#0..#00#..00.#.10.#....#.#.#....#
0#.##.###.#.#.0....##....#1...01#.#..#1....#...........#.
...#...#..#.##.#..1...#...#...........#...##...#.#.###1..
..#......#...#.#.###....##........#........10...#1......1
.....0..0..1##.#....#.#.............10..........0.#..##.1
..#..1..#..#.#.#.......0#........#..##1.....####...1##..#
#....#...........#..#..#........#..#.#.1..######.#.#.1.##
#.#....11.###..#....#.............1#...#....#....0##..0.1
..##..#..##.0#1..##0.............##.#..#10............###
0.#.###.#..##0..#.##..1###......#.#....#0....#...###....0
.#.....##....110.#100.1.....1.#.........#......1#..#.0.#1
...#....#.##..#.#....1.....1..#.#.#..#..#1...#0...#......
.##.1###0........#..#.....##..##0..1##...1###.#.....#0...
.#1...#1...............#.#.......#1...01..#..#.#0.#..#...
#......#......#...#.#01..........0#.#1...........##1.....
.1###...#..##0...#.##11#....#....#....####.##..###.0.#...
#1..0##.....1##....1#..........#.......1#.....##.#.#.#...
..#........#...........#1...#.#...#.............#.#.....#
##..#.....##....#.....#...#...1.##...#0.....#00..#......0
#....0.0....###11...#.##...#0..........#.......01.#0.....
..0##.0..............10#...#0......0..#1.#.#####0##..#1..
0....#.#1.......##......#...#......#..0..1..#..##...#..#1
..............#.111.##....##.......#......##.......1.01##
..#...........001..##.#..0##....1#...#.......###.#..0#.1#
.#11.#..#...#.#......01#..##0....1..0.##..###1..#.#1....0
##...#..#1...#.#.#..##..#..#.#.0....#.0.#...#.###1##.#...
.0.....#.#1...##...1#.#11....0#0...1.0..##......0.##.....
01....1....#...100..........#1#....0#1....#....#.1.##..0.
.....1#0..#.#.#.#1............#0..#1##...#0.#...100..#.#.
01..#..#1..##...............0#.##.#.#......1##....#..#..#
........####....#...#......#....0#..#..0.#....##1......##
#.....##....0##.........#..#.#..#.##...#...0#1.#1.......0
0....#.#..##.##.......#.##..#....#.###1...#1.......#.....
...#..##01.....1....#.#..........01..####.00#..1#.#......
..#..#.......#.1...#.........#.#......#.....##.....1#....
......#.0......##.....#####1...0............#..#0.01.#...
.....#..#....#.........#0##.....#..............00#.......
#....#...0.##...#........01#.#....0.........#..1..#......
.###.#...#...#..##....0.#1.#.....#.........#...#.#.#.....
.#1....#.#...01#...##0####.#......#...#.#.....1..#..#..#.
..##.0#1#.##..#...#..0#.#1..#....0#.#.#.###..#1..###0#0..
....#.#.....##1#1...#0#10##1......#..##.10.#.###...#0.0..
001.....#.0###.1...1##.#..0#0...##....###.1....####.#....
Target maze:
..1...11.###......0##.#.#.1#...###1..0.#.#....#.......#..
#..#.....#...#..#......0.##..0.....###......#......#.1#..
1#01#.....1##..##1.#...0.....##.#..#....#..###.#1..0#.1.1
....1...0.....#1...##...#.#.....#.#...#1#.#.#..1.....#...
..#00.1...#.......##..#..#.#0.####........#.1#...0..#....
..#...###.......#.#..#...#0.#...1#.#.......1...#...#....#
.#....##..##....##...#...#1....##...1##...#..#..#..0.#.1.
......1..1..#....1.......#.......#.1...##...#..0..#..0...
.11...#0....0###..####.#.01..#..0..#.##.#....#...#..1....
#..##..1...#.##.1##....0#.0.#..#.....#...1#11.0#.#.#....#
.#.##.###.#.#.....1##....#......#.#..#..1..#......0....#.
...#...#..#.##.#....1.#0..#.0.0....1..#...##0..#.#.###...
..#......#...#.#1###..1.##....0...#..1.1...0....#......1.
1...1.0.....##.#..01#.#1........011...............#.0##..
..#.....#..#.#.#...01...#........#..##.0....####....##..#
#....#...........#..#..#1.......#.1#.#...1######.#.#..0##
#.#......0###..#....#.......0.1....#1..#....#.....##1.1..
.0##..#..##0.#...##..............##.#0.#..............###
..#.###.#..##.0.#.##..0###....1.#.#....#.....#1..###.....
.#..1..##.11...1.#...0...1.0..#....0....#.1..1.0#..#...#0
...#.0..#.##..#.#.............#.#.#..#..#.0..#...1#1.....
.##1.###.........#..#.1...##..##....##....###.#.....#....
.#.0..#..0.............#.#.......#.0...00.#.1#.#..#..#.0.
#......#.....0#1..#.#.............#.#............##..0.1.
..###...#1.##1...#.##..#.1..#....#....####.##..###...#...
#...1##.0....##.....#..........#..010.1.#.0...##.#1#.#...
.1#........#..1....1..1#...0#.#...#..00...0.....#.#.....#
##..#.....##....#1....#...#...0.##...#.1....#...0#.......
#..0..0.....###0....#0##...#.....1..1..#..1...01..#1.1...
.0.##..1..1..1..1......#0..#.......0..#..#.#####.##0.#...
.....#.#0.......##...0..#...#..1.0.#........#..##..0#0.#.
..........1...#.....##....##1......#...0..##..0........##
..#.1..............##.#...##1....#.1.#.......###.#...#..#
1#...#..#...#.#........#..##.........1##..###...#.#.0...1
##...#..#....#.#.#0.##.1#..#.#......#..0#...#.###.##.#010
.......#.#....##....#.#.....1.#.0...1.0.##.......1##.....
.....1.01..#0.....1.....1...#0#...1.#.10..#....#1.0##0...
.0....#1..#.#.#.#......1......#...#.##01.#..#......1.#.#.
...0#..#...##.0..............#.##1#.#.......##...0#0.#..#
.0......####....#1..#..1...#0....#..#....#...0##.......##
#..0..##.....##.011.....#..#.#..#.##..1#....#.1#.1.......
....1#.#..##.##.......#.##..#....#.###.0..#........#....1
...#..##............#0#..0..........0####...#...#0#....1.
..#..#1..0...#.....#.......1.#.#......#.....##.....0#....
......#.1......##.11..#####.........0.1.....#..#.1...#...
..1..#..#....#....0...0#.##.....#0.1...1......1..#.......
#00.0#.....##...#...110....#.#....1..1......#.....#.1..1.
.###.#...#.00#..##......#..#....0#0......0.#...#1#.#.....
.#..1..#.#.....#...##.####.#......#0..#.#......1.#..#00#.
.1##..#.#.##..#.1.#...#1#..1#.....#.#.#.###0.#..0###.#...
0...#.#.0.1.##.#....#.#..##.......#..##....#.###...#.0...
....0...#..###1.0.1.##.#0.0#..00##....###..0...####.#....
" | |
|
| 7) | |
| | | Returns:
"seed = 8
W = 34, H = 47
Balls in maze = 85
Start maze:
.#4###.......##.#..#..1..1..#..#..
#...#.....#...#..#2.#.....#0.###..
.#.....##.....#....#......##.....1
#.#....#....####.......3#.##.#..#7
....5###.###.......4########..#.##
.#.#....#.#...#.#.#.2..#.#..#...#3
.###.#....#.#.#..##...............
#.#.......7##.....#..#.#.....#..#.
..55....7#.......4#..............#
.#.#.....7.#..###...#...#..#.#.#.#
....#..##..#....#.....##.#6#....##
.........#6..###..6##.....#......0
..#.....#6#.##...#....##..####...5
..#....#............##....#.4#....
..#..#...####.#.#.##.#...#...7.#..
..#.#.##.##.##..##...#....##..#.#.
......4.#7...##..........####...#.
....#.#.#5.##....7#.....7#........
....#..6.....#....##....#6#.#.#...
...#.##3#.....3##.....5...#...#...
###...3.#...#6.#..#...5#.####...3.
#.#....4...#...##....#......3.#.#5
.#.....#........#..#.#2...1#0.#..7
#....#..#..#....6#.#.7#.##7#...#..
..............#15...#....4......#.
#..#.#.##.##..##..#.......#2......
...............#...#.2.#...##..#.#
#..#.#...#..#....5.4.6....##..#...
.......5#..##5.###..##.....#.#6#..
..#.#.........###74..#....#.#....#
#.#...#.#..#.#..3##.#7.##.#4.....#
.2#..#.........#.#.........#.#.#..
##.1.#...#..#..#..............#.#.
...#..#.#.........#.#....###....##
.#.#.#....#....#..4###..#......#..
.........7###.#.......##.#......#.
#0...##.....#......#.........###..
..2......2###........##..#....#...
.##..###.##............#0.........
.4#......#2.#.#..#3.###.#.#.#...#.
###..##...##..#...##..##0....#..#.
..#....#..##..#.0#..##............
.#........##....##.............##.
..#..#.#.........#.3.#.#.....#...#
..##.7.....#.....#.#.#....#.......
#.#.#..........#.....#...#..#....#
....#.#..##.#50###...2##......0###
Target maze:
.#.###.......##.#..#........#..#..
#...#.....#...#..#.2#....1#..###.7
.#4....##.....#....#..1...##......
#5#....#....####........#.##.#..#.
.....###.###........########..#.##
.#.#....#.#...#.#.#....#.#..#..0#.
.###5#....#.#.#..##..3.......1....
#.#.....7..##.....#..#.#..6..#..#.
.7.......#.4......#............2.#
.#4#.......#..###...#...#..#.#.#.#
....#..##..#..6.#4....##.#.#....##
..5......#..6###...##....2#.......
..#.....#.#.##...#.3..##..####....
..#....#.6.....6....##..7.#..#.7..
..#..#...####.#.#.##.#...#.....#..
..#.#.##.##.##..##...#....##.4#5#.
....7..6#....##..........####...#.
....#.#.#..##.....#..1...#........
....#..3...3.#....##5...#.#.#.#.50
...#.##.#.7....##........6#...#...
###.4...#...#.6#..#....#.####.7...
#.#.2......#...##5...#.2......#.#.
.#.....#........#..#.#.....#..#..3
#....#..#..#.....#.#..#.##.#...#..
..............#.....#0.........3#2
#..#.#.##.##..##.5#.67....#.......
.....5.3.......#..1#...#...##..#.#
#..#.#...#..#...7..4......##..#...
........#..##..###..##.....#.#.#..
..#.#........5###7..5#....#.#....#
#.#5..#.#..#.#...##.#..##4#7..6..#
..#..#.........#.#.........#.#.#..
##.2.#...#..#..#..............#.#.
...#..#.#...2.....#4#7...###....##
.#.#.#....#....#...###..#......#..
...7......###.#.5.....##.#...3..#.
#....##.....#......#.........###..
..........###......3.##.4#....#...
.##..###.##.....0......#..........
4.#......#..#.#..#4.###.#.#.#...#.
###..##...##..#...##..##.....#..#.
..#....#..##..#..#..##............
.#....02..##....##.............##.
..#..#.#.........#3..#.#.....#...#
..##0..7...#.....#.#.#....#0......
#.#.#..........#.....#...#..#..0.#
....#1#..##.#..###2...##0......###
" | |
|
| 8) | |
| | | Returns:
"seed = 9
W = 55, H = 41
Balls in maze = 328
Start maze:
.0.....0##....0#0...1###....##.#..10##1..0....#....0#.0
....#.#...#.#.#.....##.1##10...#..#1#...#....00#..#..#.
1..0#.......#.1..#.#111...#...1#...11#.##.#.....0##....
..##...........#.0##...1##00#.......###..1..##....#1.##
#..####.#...#.#.11..1#.#1#.1..........0.#.001.1#0#1.##0
#.#..#..1#1.##.0#...1..........0#....#.....#......0#01.
...#.#1.........#..###.................11.#..#0.....0.#
##..........#.##....0.##..#.#..#.0#...1..#..###..1#..#.
1#..##..#1..........#1#0......#.......0#..#..#..#0....1
..11#.....#0#..#.#.11........#0..#.....#.##0....0.#.#.#
..#..###...#0..1....##.....1##..0##............1.#....0
..##...#..#1....#.#.#0.#....#..1..#..#.#1...#....1.....
#..##.#.......#......10..1#..#1###....#.##.#..##..#....
...#...........#.#...##.#.0.#.#..#0...#..##....##......
..#1#.....##..#00.....##......#.0......0#.#0.1..###..#.
#0..1#..#.10#.###.#..#1#...#....##..###00.####.#1.#.##.
.0..........#####.#....#...##..##1....00...........#1..
1.....1##..##.#......#.010......1...#........00.1.....#
01#.........#....#.....1###...##......##0.##..#..1..#.1
.###....101..#...##1...#.....#0.....#.##.......###.#...
.#1......0.1#.#.#1.1#..1.#....#11.1.0###0......#....0..
1#..0#.#....#..10.###.#.......#.#.##.#1.#.#..#0..#.##1.
1.........#1..1#....0#1.#.#.##.#1#11#0......#1....1##.#
....##...#.1##.1..##.#.......1#...#.0.0##.#.0##11....0.
0..#0.......0..01....#...###1.00.##...###0.0...#..1..1.
#.....#...#1.#...#..#......1#.1.1###...#1...#.1...0.0#.
....#.....#1#.......#0#0.#.....0...1..###1#.......##0..
.....#.#...#0..........#..#...1......0#11#....1...0#.11
.#1.................0#.....11.0......#.00..0..#0#0.#...
.#..#..#....00..#..#1..#....#1...0#.1....0110.##10....0
1#..#..#.#1.##1...10.101.....#.....#0......#..#...1#.##
#..#0.#....111#......1.......0..0.11.#.....101###1..#.#
0.0#.#0....#..1#.#####0...#1.0#.#000.0.##...###00.#....
...........0#..#0...###..#.01...0.#.........####.0#.#..
#......#...#0........#1..0..#..#..0...11#......#......1
....0#.1..0...1.0.####0.1.##...#0..##...1.......1...#..
....0#...0#....##.##...##0..0....#.#1.#...#.###........
..#.###..1#.0#..1...##..#...#.##.#.#.011..........1...1
..0....#1.##0.##.0...#1..0...#..##.....#....#..#.0.##.#
...###.#.1..#....#.#.0#....##..#...........0..........1
.....0..0.....1##...11##1.0#.......#0..#...#0..00#...0#
Target maze:
........##0.1..#.....###0...##.#..0.##......0.#.0...#0.
....#.#...#1#.#.....##1.##.1..0#..#1#1..#0..1..#..#.0#.
0...#.......#....#.#.1....#0...#.1...#.##.#0.....##1...
.0##.....010...#..##11.1##.1#.......###.....##....#..##
#..####.#...#.#....1.#0#.#1.1.....1.....#..1.1.#.#.1##.
#.#..#...#.1##.1#.10...........1#....#.....#....00.#0.0
1..#.#..........#.1###....0...............#.1#...0....#
##1.........#.##...1..##..#.#..#..#..1.1.#..###1..#..#.
.#..##1.#.1....10...#.#....1.1#100.00..#..#..#..#..11.0
.0..#.1...#.#..#.#..01.......#...#...0.#.##...0..0#.#.#
..#..###..0#...0....##.0....##0..##..0...........#.....
..##...#..#....1#.#.#.0#..1.#01...#1.#.#....#1.........
#1.##.#...1...#1..1......0#.0#.###..0.#.##.#..##1.#0...
...#...........#.#..1##1#...#.#..#.0..#..##....##......
..#.#.....##.0#..01...##...010#......0..#.#.....###..#.
#....#..#...#1###.#..#.#...#....##..###..1####0#..#.##.
1.....00....#####.#.1..#...##..##........1........0#..0
.1...1.##..##.#..1...#.1............#0......0.......1.#
..#1........#....#.011..###...##......##.1##..#...10#..
1###.......1.#...##....#.....#1...0.#.##.1...11###1#0.1
.#.......1..#.#.#...#....#..1.#......###.0.....#......1
.#0..#.#...1#1....###.#.01....#.#.##0#..#0#0.#...#0##.1
.....0....#..1.#.....#..#0#.##.#.#1.#...11..#0.....##.#
0.0.##...#11##1...##.#..11....#01.#01..##.#.1##.....0..
1..#....1.01.....0...#...###....0##1..###...0.1#.......
#.....#.0.#00#.10#..#0......#....###.1.#..01#0...0.1.#.
.1..#....1#.#....1..#.#..#...011....1.###.#.0.1...##...
.0...#.#...#.0........0#..#...0.......#.0#.001.0...#1..
.#.......1....01.0.01#10..0.......01.#......1.#.#..#1..
.#..#..#..1.....#..#.11#1...#...11#..0001.....##....0..
.#..#..#.#..##.10...11..0..00#.....#......0#.1#...0#.##
#..#..#...1...#.....................0#.0......###...#0#
...#.#.....#...#.#####..0.#...#1#...0..##...###..1#0...
.0.......0..#1.#.0..###..#...00...#.1.0.1...####..#.#..
#......#...#..0...1..#..1...#..#.1.10...#0...1.#.......
0....#0..0.0......####.1.1##0.0#..0##....1.....0.1..#..
0....#....#0...##1##1..##..0.....#.#..#...#.###........
..#.###.1.#0.#.0....##..#...#.##.#.#0...1.011....10....
1......#..##.1##..1..#..0...0#..##..01.#....#..#...##.#
...###0#...0#...1#.#..#....##..#.......10...0....01....
...0.........11##.1..0##...#..0....#...#.0.#10...#....#
" | |
|
| 9) | |
| | | Returns:
"seed = 10
W = 11, H = 29
Balls in maze = 52
Start maze:
..000.#....
...#.......
00.........
...........
0..........
..........0
..0......00
.....0....#
.....0....#
....#...#00
0..0.......
..0........
0...#.0#...
0.....#.#..
00#0..##.00
00.......00
0........0.
....#.#0...
0...0......
.#.........
#..........
.........00
#0....#000.
......#.#.0
#.....#.#.0
0..........
0.0.....#..
.....00.#..
.0#0.0...00
Target maze:
.....0#....
...#....00.
...........
....0...0..
..0........
.....0..0..
0..0.0.....
0.000.....#
.0.....0..#
....#.00#..
..0......00
....0.....0
....#..#...
......#.#..
..#..0##0..
......0....
.....0..0.0
00..#.#...0
...0...0..0
.#.........
#.0....0...
0.0...0.0..
#.....#.0.0
..0..0#.#..
#.00.0#.#..
...........
........#0.
........#.0
0.#........
" | |
|
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)2020, TopCoder, Inc. All rights reserved.