JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Final Round
Problem: XplosionMan

Problem Statement

    

You are given a square board containing N by N cells. On the board you have destructible walls, non-destructible walls, open spaces and power-ups. You control a character called the Xplosion man who can move around, collect power-ups and plant bombs. The Xplosion man can move through cells with planted bombs without any effect on them, but cannot move through either type of walls. A planted bomb will explode after T turns and it will destroy objects lying in a range R in the same row or column as the exploding bomb. The effects of the explosions on different types of objects are as follows:

  • Open space : No effect.
  • Non-destructible wall : The wall remains, and the explosion does not propagate beyond the wall.
  • Destructible wall : The wall is destroyed, and the explosion does not propagate beyond the wall. The destroyed wall will prevent any other explosion during the same turn from propagating beyond it.
  • Power-up : The power-up is destroyed, and the explosion propagates to cells beyond it.
  • Planted bomb : The bomb explodes and the effects of the new explosion are handled recursively.
  • Xplosion man : No effect.

You earn points by destroying destructible walls. After each bomb explodes, your score increases by the square of the number of walls destroyed with all explosions triggered by it. Your task is to maximize the sum of the scores gained during individual explosions.

Implementation Details

Your code should implement the method makeMoves(String[] board, int T, int B, int R). Your makeMoves method will be called once and should return a String containing the actions of the Xplosion man. You are allowed to make a maximum of N*N*10 actions.

  • board gives the board containing N by N cells. Each element of board describes one row of the board. '.' denotes an empty space. '#' denotes a non-destructible wall. '+' denotes a destructible wall. 'T', 'B' and 'R' denote time, bomb and range power-ups respectively.
  • T gives the initial time that a planted bomb takes before it explodes. Collecting K-th time power-up will increase the time between bomb planting and bomb explosion by K (each next power-up is more powerful).
  • B gives the initial number of bombs that you have available to plant. Collecting each bomb power-up will increase your amount of bombs by one. Once a bomb has exploded, it will be available to be planted again.
  • R gives the initial range of the explosion that a bomb will cause. Collecting K-th range power-up will increase the range of explosions for bombs planted in future by K (each next power-up is more powerful). Once you planted a bomb, the range for that specific bomb will remain fixed even if you collected a range power-up before it exploded.

You must return the list of actions that the Xplosion man will perform. Each character of your return describes one action. ROW is the zero based row and COL the zero based column of the board. The top left corner of the board corresponds to row and column zero. The Xplosion man always starts at location (1,1). The possible actions are:

  • U : Up, moves to location (ROW-1, COL).
  • D : Down, moves to location (ROW+1, COL).
  • L : Left, moves to location (ROW, COL-1).
  • R : Right, moves to location (ROW, COL+1).
  • B : Plants a bomb at your current location (ROW, COL) if there is no bomb there yet.
  • T : Set the bomb timer of the planted bomb with the lowest bomb timer to 1. This bomb will explode in the next turn. If there is more than one bomb with the same lowest timer value, the one in the lowest row will be chosen. If there is still a tie, the one with the lowest column will be chosen. Only one bomb is affected.
  • If you attempt any invalid action, it will simply be ignored and the simulation will continue.

The sequence of events for each action follows:

  1. Decrease bomb timers for all planted bombs by one, following a row column major order.
  2. Once a bomb timer reaches zero, the bomb explodes.
  3. A bomb explosion might trigger more explosions which will be handled first before moving on to decreasing the timer of the next bomb.
  4. Your action will be processed and the board updated accordingly.

This sequence is repeated until there are no destructible walls left or when you don't have any actions left to perform. The simulation stops immediately after that, and any bombs left on the board after that don't explode.

Scoring

For each test case we will calculate your raw and normalized scores. If you were not able to produce a valid return value, then your raw score is -1 and the normalized score is 0. Otherwise, the raw score is equal to the sum of scores over all explosions. The normalized score for each test is 1,000,000.0 * YOUR / BEST, where BEST is the highest score currently obtained on this test case (considering only the last submission from each competitor). Finally, your total score is equal to the arithmetic average of normalized scores on all test cases.

You can see your raw scores on each example test case by making an example submit. You can also see total scores of all competitors on provisional test set in the match standings. No other information about scores is available during the match.

Test Case Generation

Please look at the visualizer source code for the exact details of test case generation. Each test case is generated as follows:

  • The board size N is randomly selected between 21 and 61 (inclusive).
  • The number of power-ups is randomly selected between 5 and 50. All types of power-ups are equally likely to be selected.
  • The fill ratio P is chosen between 0.6 and 0.9. This determines the number of destructible walls on the board.
  • The initial values of T, B and R is independently randomly selected between 1 and 5.
  • All values are chosen uniformly and independently, at random. Ranges are inclusive.

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, simulation and score calculation.

 

Definition

    
Class:XplosionMan
Method:makeMoves
Parameters:String[], int, int, int
Returns:String
Method signature:String makeMoves(String[] board, int T, int B, int R)
(be sure your method is public)
    
 

Notes

-The time limit is 20 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes.
-There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB.
-The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here.
-There are 10 example test cases and 50 full submission (provisional) test cases.
 

Examples

0)
    
seed = 1
N = 21
T = 2
B = 2
R = 2
#####################
#...+++++++++.......#
#.#+..#.#...#+#.#...#
#.B.+.++....++....B+#
#.#.#T#.#.#.#+#.#+#.#
#+....+++..+...+..+.#
#.#.#.#.#.#+#.#+#.#.#
#......+.++..T......#
#.#+#.#..+#+#.#+#.#+#
#++..+.+.....++....T#
#.#.#+#.#.#+#.#.#.#+#
#..++.++.+.....++...#
#.#...#.#+#.#.#.#T#+#
#...R.T....+.+.+....#
#+..#.#++T#.#+#+++..#
#....++..+...R.....+#
#.#+#.#.#.#..+#.#+T+#
#+......++++.+.....+#
#.#...#.#.#.#.#+#+#.#
#.....+.T...+.......#
#####################
1)
    
seed = 2
N = 35
T = 5
B = 5
R = 3
###################################
#.....++++++...+..++R..++......+..#
#.#+#.#.#+#+#+#.#+++.+#.+...#.#.#.#
#.....+.++.R.+.B+R+..++...+.++.+..#
#+#.#.#.#.#.#+#.#.#.#.#+#+#.+.#.#+#
#..+++..+++..+..+++.......++++....#
#.#.#+#+#.#+#+#.++#+#.#.#.#.+.#.#.#
#.+....+.+.+..+B.+..+.+++.+..+..++#
#.#.#.#.#.#+.+#.#+#.#.#+#.#.#.#+#.#
#T.+.+.++.++......+++..+.+..+...+.#
#.#++.+.#.#+#+#R#.#.#.#+#+#.#+#.#+#
#R+.+.+.+.++....+..+.++...+++.++..#
#.#+#+#.#.#.#.#.#.#+#+#.#.#+#.#.#+#
#..+....++...+.......+.+.++...++..#
#.#+#+#.#+#.#+#.#+#+#+#+#.#...#.#.#
#T..+..+..++..+..++..++.+..+B..++.#
#.#.#.#.#+#+..#.#.#.#.#.#.#.#+#.#+#
#++..++.+.T+..+..+.+B+....+.++++..#
#.++#+#+#.#.#+#.#.#.#.#T.+#.#..+#.#
#++..+++....+..+++....R.+RB++...+.#
#.#.R.#.#.#+++#.#.#.#+#..+#+#.#.#.#
#R.+.++..+........+.+.+.....++++++#
#B#++.#.#.....#.#+#++.#.#+#+#.#...#
#++++....++++..+..++..++.+.R++..+.#
#+#.#.++.+..#+#R#.#.+.#+#.#+#+#+#.#
#......++..+++..++..+.+.+.B+..++..#
#.#+#...#+.+#+#++.#+#.++#+++#+#.#.#
#.++.+.++....+.T..+....RT+..++..+.#
#.#.#B#R#.#+#...#+..+.#.+.++#.#.#.#
#.+.++++.+.+++......+..........+..#
#+#.#+#+#.#+#.#.#.#.#.#+..#+#+#.+.#
#+++++.++...++B.++..+.++..++...+..#
#.#.#+#+#B#+#+#.#+#.#...#.#+#+#+#.#
#..+B.++.+T++++....+R+..++.+..+..+#
###################################
2)
    
seed = 3
N = 29
T = 5
B = 3
R = 1
#############################
#...+..+++..++.+++...R+.+...#
#.#.#.#.#.++.+#.#.#.#..+#.#+#
#..+T.+.B...+..+..+....++.+.#
#.#.#.#+#.#.#.#+#.#.#+#.#.++#
#...++.+.+..+.+..+.+.++.++..#
#R#..T#+#+#.#.#.#T+.++#.#.#.#
#.++.++R...+.R.....+.+.....+#
#B#+#R#.#.#B#.#T#.#...B.#.#.#
#....+B........+.....B...+..#
#.#.#.#T#B#.+.#...#...#.#R..#
#+.+.+.+..+T......+.+++++..+#
#.#.#+#.RR#+#.#..+#+..#...#.#
#...+...+.++.+.R.+R...+...+.#
#.#.#.+T#.#.#.#.#+#..+#+#+#+#
#....R.....+.....++....+.R++#
#+#.#..+#+#+#.#...#.#.#++.#.#
#+.+R.+..++R..+++...+.+....T#
#.#.#T#+#+++#R+..+#.#.#..+#+#
#+.+..++T..+++++..+.++.+R..+#
#.#+..#.#..+#.#.#+#.#B#.#.#+#
#....++++.B.B.R..+B++.R.+...#
#.#.#.#.++.R#.#.#+#+#.#.#.#.#
#.+....T++..+.+..+.+.T+..+..#
#.#...#.#.#.#.#.#.#.#+#.#+#.#
#++.R+++++.R.T+...++++++..++#
#.#..++.#.#+#.#.#+#+#.#+#.#.#
#.++......+++.+.+..+.......B#
#############################
3)
    
seed = 4
N = 31
T = 1
B = 1
R = 4
###############################
#...T+...+.+..++.+..+.++.+++..#
#.#.#+#...#.#+#B#+#.#+..+.#+#+#
#.........++..+..++...+.+.+.+.#
#+#.#.#.#.#+#.#.#.#.#..+#.#.#+#
#++......T...+.......++.+.+..+#
#.#+#+#...#+#.#+#.#.#.#.#.#+++#
#.+.++.++...+....+....+..++...#
#.#+#.+....+#+#+#..+#.#.#+++#.#
#++..+........++.+..+.........#
#.#..+#.#+#.#.#.#.#+#..+..#.#T#
#..++.+.+...+.+..+..++..+.+++.#
#.#+....+.#.#.#.#B#.+.#.#.#.#.#
#+..+..++.+....B........+...+.#
#R#..+#.#.#.#.#.#.#.#.#+R.#+#.#
#.B+...+++++.++..+....+++.R+..#
#.#.#.#+#.#.#++.#+#.#+#+#.#.#.#
#+.+...T+.......+..+.++...++..#
#.#++.#.#.#.#.#+#.#.#.#.#+#.#.#
#..........+.......+..+R+.T+..#
#..+#.#.#.#.#+#+#+#.#.#+#.#...#
#.++..+.+....+.++..++..+......#
#..+#+#.#.#+#...#+#.#.#+#+#+#+#
#.....B...........+..........+#
#..+#+#.#.#.#.#.#.++#.#+#+#.#.#
#.+.....+.+....++...........+.#
#..B#.#.#..+..#.....#+#T#+#+#+#
#+..+.....+...+.....+.R...++..#
#.#+#...#+#+#.#+.+#+..#+#.+...#
#+....+.T....R.+.........+....#
###############################
4)
    
seed = 5
N = 49
T = 5
B = 1
R = 3
#################################################
#....+..+.+..+.+..++.........+.+..+...+++.+...++#
#.#+#+..#+#+#...#.#+#.#.#..+#.#+#.#.#.#.#..+#.#+#
#+.+.++..+..++....++.....B...+.+.+......++..+.R+#
#.#.#.#.#+#.+.#.#..+#+#+#+#..+#.#.#+#..+#+#.#+#+#
#.++.++.....++.+.++.....+..+.+.++.+++..++.+.++++#
#.+.#++.#.#+#+#.#.#...#+#..+#.#.#.+.#.#+#+#..T#.#
#..+...+..+..+...+.+..+...++..+.+.+.+........+..#
#.++#.#+#+#+#++.#+#.#+..#.#.#+#.#+#.#+#.#.#.#.#.#
#....B+.......+...++...+..+..+.++...++..+.+++.+.#
#...#..+++#.++#.#.#.#.#+..#.#.#.#+#..+#.#.#.#B#+#
#+..+.T.+..+........+R+.+.++....+++.++..+.+++..+#
#+#.#+#+#+#+#+#+#.#.#.#.#...#+#.#+++#+#...#.#.#.#
#+..+++..+..++.+T+....+.+++++.+.......+.++++..+.#
#+#.#.++#..+#+#.#.#.+.#.#...#...#+.+#.#.#+#.R+..#
#..+......+.++.+..++++.++.+.+++.++.+..+.+..+....#
#+#.#.#+#+#..+#.#+#.#+#.#+#+#+#+#.#.#.#.#.#+#+#.#
#++.+.+.+........+++.....+......++..+..+....+...#
#+#.#.#+..#...#+#+#.#.#.#.#+#.#...#.#...#.#...#.#
#.........++.+..+..++..+..+.+...++.++.....+R.+.+#
#.#.#+++#+..#.#.#+.+#++.#.#+#+#.#...#.#.#+#.+.#.#
#.++.+....++.......+..+.++..+..+++.......++++...#
#.#.#.#.#++...#+#+#.#+#++.#+#.#.#.#.#.+.#+..#.#.#
#++..+.++......+..++..+...++...+..+.+..+.....++.#
#+#+#+.+#...#+..+.++#.#+#.#.#.#.#.#.#+#...#+#+#.#
#..++..+.++++.B..++......++....+...+.........+..#
#+#+#.#.#+#.#.#+#+#.#.#+#.#+#..+#.#.++#.#.#+#+#.#
#..+..+.+.++...+.++....++...+..+.++..+.+.+......#
#.#.#.#.#+#+#.#.++#.#..+#+#+#+#.#+#+#+#+...+#...#
#.+++..+.+++.+....+.......+.+...++.+..+.++.+..+.#
#+#...#+#.#+#.#.#.#+#.#+..#+++#.#.#...#.#+#.#.#.#
#+...++..........+.+.++.+...+...+++.+.+++++.....#
#.#+.+#.#.#...#.#.++++++..#.#+#+#.#.#.#.#B#.#.#.#
#+......+......+.+++.+..+.+..+....++..+...+..+.+#
#+#.#.#++R+.#.#.#+#.#.#+#.++#.#.#.#.#.#+..#.#+..#
#.+....+...+B....+++....+.T.+...++..+.....++.++.#
#.#.#.#+#.#.#+.+#.#+#.#+#+#+#.#.#+#+..+.#.#+#+..#
#B..+.+++.+..+...+.+...+++.+..+..+..+++.....+...#
#.#+#.#+#.#.#.#+#T#++.#+#+#.#.#.#+#.#.#.#.#.#+#.#
#...+++..++++.++..+.+++.+++++......+.+..+.+.+...#
#+#...#.#+..#.+.#+#...#.#.#+++#+..#.#.#+#.#.#+.+#
#...++++R....+++...++....+++.++.+++.....+++.....#
#.#.#.++#.#.+.#++..+.+#.#++.#.#+#.#+#+#.#.#.....#
#........++....++....+.++...+...+..+.+...+...++.#
#+#.#.#+#+#.#.#....+#+#+#.#+#.#.#.#.#+#.#.#+#+#.#
#+...+++....+.+.++.+++..++..........+..++......+#
#+#+#+#.#.#.#.+.#.#.#.#.#...#+#+#++.#+#+#.#.#.#+#
#.+.+..T+...+++...+.+..++.+....+..+.+B.+++.++.+.#
#################################################
5)
    
seed = 6
N = 53
T = 1
B = 5
R = 3
#####################################################
#.........+...+......+.+.............++...+......+..#
#.#.#...#+#.#+#.#.#.#.#.#.#.#.#.#+#.#+#.#+#.#+..#.#+#
#.........+++....+++.....+........+..+..+.+.........#
#.#.#...#.#.#.#.#.#+#.#+#+#+#+#.#.#.#.#.#...+.#.#.#.#
#........+..........+.+............B.+..+....++.....#
#.#.#.#.#+#.#.#..+#.#+#.....#...#+#..T....#+#.#..+..#
#+..+.+..........+...........+..+.+..++.........+...#
#.#+#.#+..#.#...#.#.....#.#..+#.#.+.#.#.#..+#+#+#+#.#
#...+..............+.............+.....+............#
#.#.#+#.#.+...#.#+..#.#.#.#B#+#.#.#.#.#...#.#+..+.#.#
#..+++....+...+.......+..++.+..+.......+..++..+....+#
#.#..+#.#.#.+...#.#.#.#+#.#...#.#.......#.#+..#+..#.#
#..............+...+++...+....+..+.+.+.+.+.....+....#
#.#.+.#+#.#.#.#+#.++#+#.#.#.#.#.#+#.#+#.#.#.#.#.#.#+#
#.+..+....++.+.+.+...++.+.+..+......+........+...+..#
#.#.#.#.#+#.#...#+#.#+#.#.+.#.#.#.#+#+#.#...#...#.#+#
#.......++.+.+..+..+.+.++......+..+...+.............#
#.#.#.#.#.#.#.#.#.#...#.#.#.#.#.+.#.#.#+#.#.#.#.#+#.#
#...+.....+...+..+...+.+.....+.+.+.......+...+...+.+#
#.#+#+#.#...#.#.#+....#++...#...#.#...#...#.#+#+#.#.#
#.....+.+..+..+.....++....+...+..++.+.++.+.+..+.+.+.#
#+#.#.#.#.#.#.#++.#.#.#...#...#.#.#.#.....#.#.#.#...#
#.+.........+..+..B...+.......+..........+..........#
#.#.+..+#.#.#.#+#.#.#.#.#+#+#.#.+...#.#.#.#.+.#+#B#.#
#..+++...........++.....+.......+.+...............+.#
#.#.#.#+#.#.#.#+#.#.#.#.#...#.+.#.#+#...#.#.#+#+#+.+#
#.................+...............++......+..+......#
#.#.#...#.#.#.#+#.#.#..+#.#.#.+.+.#.#.#+#.#.#.#.#.#+#
#...........+.+...+...++.....+.....+...+..+.........#
#+..#.#.#...#.#...#.#.#T..#.#.#+#+#+#.#.#.#.#.#.#.#.#
#+.......+.......+..++...++........+.....+..........#
#.#.#.#.#...#.#.#...#.#.#.#.#.#.#.#+#+.+#.#.#.#.#+#.#
#+........+..+...++.+............+........+R..+..+.+#
#+#.#.#.#.#.#.........#.#.#+#.#.#+.+.+..#.#...#.#.#+#
#.........+........+......++...+.+.........+.....+..#
#.....#+#+#.#+.+#+#.....#.#.#.#.#.#.#.+++.#+#.#.#+#.#
#........+......+.+......++..+.+.............++.+...#
#...#.#.#.#.#.#...#.#.#+#.#.#+#.#...#...B.#.#.#.#+.+#
#............+....+.+.+.++.......++.....+..+........#
#...+.#..+#.#.+.#...#.#.#...#.#+#+..#.#T#.....#.#+#.#
#+.+.....++......+..+....T..........+.+.............#
#+#.#..+#.#.#+#+#...#.+.#...+.#+#...+.#.#+#.#.#.#+..#
#...+.........+.++...+.+...++............+..+..+....#
#.#.#+..#.#.#+#.#.#.#.#.#.#...#+#.#+#...#+.+..+.#+#.#
#.....+++..+.......+.....+++..+++.....+.....+.+...+.#
#.#...#.#.#+#+#.#.#.#.#+.+#.#.#.#+#.#...#.#.#.#.#.#+#
#++++...+.+....+.+.+..++..+..+....+...+..+........+.#
#...#...#.+.#+#.#.#.#.#.#.#.#.#...#.#.#...#+#.#.#.#.#
#.............+........+.+..++...+....+.........+...#
#.#+#+#.#..+#.#+..#+..#.#...#.#.#.#.#.#.#+#.......#.#
#.........+.+....+..+.....+.....+...+.....+..+.+....#
#####################################################
6)
    
seed = 7
N = 25
T = 5
B = 1
R = 1
#########################
#..B.....++.......+....+#
#.#T#.#+#.#.+.#++.#R#.+.#
#.....+.+...+..++...+.++#
#.#+#.#+#+#.#.#+#R..#.#.#
#+....+...+..++.++.++...#
#B#+#...#.#.#.#+#.#.#.#.#
#.....++.++.+.....+..R..#
#.#.#.#+#.++#...#..+#+#.#
#++++..++R.+.....+......#
#.#.#.#+#+#B#+#R#+..#+#.#
#T+......+....+..++....+#
#.#++.#R#.#+#...#+#.#...#
#+++T+.++.B+...+..+.+..+#
#.#+#.#...#...#.#R#.+...#
#.+.+...B+.+..+.+.+...+B#
#.#R#...#.#+#B..#.#+.+#+#
#...+++.++...+..+....++.#
#+#+#.#+#.#+#.#.#+#.#.#.#
#...+.+..++..+.+.+......#
#.....#.#.#.#.#.#.#.#.#.#
#..+.+....++.+..++...+.+#
#.+++.#.#.#.#.#.#+#.#.#+#
#.++.....+.+.+.+++...++.#
#########################
7)
    
seed = 8
N = 37
T = 4
B = 5
R = 4
#####################################
#..++T+..++.+++++........+.+......T.#
#.#.#..+..+.#+.+#+#.+.#.#+#.#...#T#.#
#..+...++.+...++.......+.T.....+..B+#
#.#.#.#.#+..#+#.#+#+++#.....#R#..+..#
#...+.................+.+.+.....++.+#
#+#+#...#...+.#.....#+#+#.#R#.#.#.#.#
#.+.....++......+.....B..+..++..+...#
#R+.#+#.#.#.#.#.#.#.#.#.#+#.#+#B#.#.#
#..+.....++++++...+..+......B+..+..+#
#+#+#.#.#B#+#...#.#...#.#.#.#.#.#.+.#
#.+..R....+....+....+.+...+.+..++...#
#.#.#.+.#.#R#.#...#.#.#+#+#R..#.#.#.#
#....B...T......+..+...++.T.....T..+#
#..+#.#+#.#.+.#.#.#+#...#+#...#+#.#.#
#.+....+......+......++...RR..++..+.#
#.#.#...#.#.#.#.#.++..#+#+#+#.#.#.#+#
#..+..+.+...+.....+.+...B.+..+......#
#.#.#.#.#.#.#.#.#+#.#.#.#.#T..#.#.#.#
#..+...+..+.......+.+.+.+....+.T..+T#
#.#...#.#+#.#.#.#+...T..#+#.#.#.+.#.#
#.+.....++....+....+.+....+.......+.#
#...#.+.#+#+....#.#.#+#.#.....#+#.#.#
#.+.+....+.......+++......+.+.......#
#.#.#R#.#.#.#.#.#.+...#.#.#.#.#.#+..#
#.+..+R.+......+..+.......+..+...+..#
#.#...+.#.#..+#+#R#.#+#.#.#.#+#.#.#.#
#....+.++..+.+.+.+R..+...+........++#
#.#+#+..#+#.#.#+#.#....+#+#.#.#.#+#.#
#.+++.++.+..+.+++......+...+.R...+..#
#+....#.#.#.#.#.#.#..+..#.#.#.#...#.#
#+......+.+++..+...+.T.+.+........+.#
#...#.#+#.#.#...#+#.#.#.#.#.#.#+#.#.#
#+...++..+.+..............+..+.++...#
#.#.#+#+#.#.+.#.++#+#...#+#+#++.#.#.#
#.+B...++.+..+.+............+..+...+#
#####################################
8)
    
seed = 9
N = 41
T = 4
B = 5
R = 2
#########################################
#..........+.........+.........+...B....#
#.#.#T#...#B#.#.#.#.#...#R#.#.#.#.#.#+#.#
#.........+....+.......................+#
#.#.....#...#.#+#...#.#...#+.+#.#.#.#.#.#
#.++..........+...+.......+.....+T.+.++.#
#.#.#.#.#.#+..#.#..T#.+.#...#.#.++#...#.#
#.......T....+............+...........+.#
#+#.#.#...#...#.#.+.#.#.#.#+#+#.#.#.#.#.#
#....+...............+...+.............R#
#.#.#.#.#.#.#.#.#..+#...#.#.#.#.#.#.#.+.#
#.....+.+...R....B.+.....+.+.....+......#
#.#...#.+.#.#.#.#.#T#.#.#.#.#.B.#+#.#.#+#
#...........R...........T+.......T......#
#..+#.#.#...#.#.#.#...#.....#.#.#.#.#.+B#
#..+............T.......+....+..++......#
#.#.#.#.#.#.#.#.#.#.#.#.#...#.#.#.#.#...#
#+..........+..+................+....R..#
#..+#R#.#.#.#.#.#.#.#.#+#.#.#.#.#+#.#.#.#
#+.........+...................+......+.#
#.+.#.#.#.#.#.#.#.#.#.#.#.#.#.#+#...#.#.#
#..............+.......+.....+.+.+......#
#.#.#.#.#.#.+.....#.#.#.#+.+#.#.#.#.#..+#
#.T..................+......+.....R++...#
#.#.....+.#.#.#.#.#.#+#.#T..#.+.#.#.#...#
#...................+.....+........+....#
#.#.#.#+#.#.#.#.#...#+#.#.#.#.#.#.#.#...#
#.......+.........+..........++..+......#
#...#+#+#.#...#.#.#.#+#..+#+#.#.#.#.#.#.#
#..+.....+....+.....R.+.+...+.+.........#
#.#.#.#.#.#.#.#+#.#+#.#.#.#...#+#.#.#+#.#
#...........+...+...+......+..........+.#
#.#..T#.#+#...#.#+#.#.#+#.#.#+#+#.#...#.#
#.....+.+..+R+...+....+...........+.....#
#.#.#.#+#.#+#.#.#.....#.#.#.#.#.#.#+#...#
#...+..B.................+...B....T.....#
#.#...#.#.#.#.#.#.#.#.#.#.#.#.+.#.#.#.#.#
#...........+.+.....+...................#
#..T#.+B+.#.++#.T.#...#..+#+..#.#.#.#.#T#
#+.+.............+.+T..+.........+..++..#
#########################################
9)
    
seed = 10
N = 35
T = 4
B = 1
R = 5
###################################
#..+......+...++..++..+..++....+..#
#...#+#+#.#.+.#.#+#+#+#..+#.#+#+..#
#++..+.++....+.++..T..++.+.+....+.#
#+#.#.#+#.#.#.#.#.#.#.#+#.#+.+#+..#
#....+......+.++..........+...+...#
#.#.#..+..#.#+#.#.#.#.#.#+++#.#.#+#
#.+B.....++++.+.....++.+...+.++.+.#
#+#.#++.#.#+#R#+#+#.#.#+#+#+#.#.#.#
#...++.+.....+.+..++++.+...+.....+#
#+#.#.#+.+#.#+#+#.#+.+#.#..+#.#.#.#
#.++..++..++..+..+++.+.+..+..+....#
#+#.#.#.#.#+#.#.+.#.#++.#.#+..#.#.#
#.+..+.+..+...++.R+....T+.R+..+.+.#
#+#.#.#.+.#.#.#.#+#+#.#.#+#+#.+.#.#
#+.+.++...++++.+.........++....+.+#
#.+.#.#.#.#+#.#.#.#.#+#.#.#+#+#.#+#
#.+.........+.....+.++..+..+.++...#
#.#.#.#+#.#+#+..#.#.+.#+#.#...#+#.#
#++..+.++..R+....++....+++.+..+...#
#.#+#+#.#+#..+#+....#+#+#+#.#.#.#.#
#..++++++.+...+++..++......+.+.+..#
#+#...#...#.#+#.#.#.#+#+#.#.#.#+#.#
#++.............++.+...+..++..+..+#
#.++#.#.#.#.#.#...#.#+#.#.#.#+#.#+#
#T+.....+.++.+....++.++...+.+..+..#
#+..#+#.#.#+#.#..T..#+..#.#.#+#.#+#
#+++.++.+.+..++.+..+.+.+.+.+.+..++#
#.#.#.#B#.#+#+#.#.#.#.#.#+#+#.#.#.#
#.++.++.....++.+++..+++.+..B.+....#
#+++#+#+#+..#+#++B#+#.+.#.#.#+++#+#
#+.+..+..+.....+.+.+....+.+.+++.+.#
#.#+#+#+.++.#.#++.#++.#.#+#..+#.#.#
#.+.++..+.T++......+......+.+..+++#
###################################

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)2010, TopCoder, Inc. All rights reserved.