BoardCoveringDiv1

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 ints N, R and C. Your task is to find any valid solution for a N times N board on which the black square is in row R, column C. (Both indices are 0-based.) Once you have a solution, you need to color its trominoes using 10 non-black colors in such a way that adjacent trominoes always have different colors. (Trominoes are adjacent if they share a side of a unit square. You may assume that any valid solution can be colored in this way.)

If there are no solutions for the given N, R and C, return an empty String[]. Otherwise, return a String[] with R elements, each containing C characters. Use the characters '0'-'9' for the ten tromino colors and the character '#' for the uncovered black square.