DrawNTrees | Topcoder Archive

Problem Statement

You have a rectangle divided into a grid of unit squares. The rectangle has R rows and C columns. You have 10 colors, represented by the digits '0' to '9'. Paint each cell using one of those colors. In the resulting painting we will look at the 4-connected components. Each of these components must be a tree. There must be exactly N trees in the painting. (See Notes for a more formal definition if this one is unclear.)

Given R, C and N, produce any one such painting and return it as a String[]. Any valid solution will be accepted. If there is no solution, return an empty String[] instead.

Definition

Class:: DrawNTrees
Method:: draw
Parameters:: int, int, int
Returns:: String[]
Method signature:: String[] draw(int R, int C, int N)
(be sure your method is public)

Notes

Consider the graph in which the vertices represent cells of the grid. Two vertices are connected by an edge if their cells share a side and have the same color. All components of this graph must be trees and there must be exactly N of them.

Constraints

R will be between 1 and 50, inclusive.
C will be between 1 and 50, inclusive.
N will be between 1 and R*C, inclusive.

Examples

```
4
```
```
6
```
```
5
```
```
Returns: {"000003", "410101", "210101", "111111" }
```
The returned bitmap: 001211 011110 000100 077111 The individual components are shown below. We can easily verify that there are 5 of them and that each of them is a tree. Note that two separate components share the same color '0'. 00.... ..1.11 ...2.. ...... ...... 0..... .1111. ...... .....0 ...... 000... ...1.. ...... ....00 ...... 0..... ...111 ...... ...... .77...
```
7
```
```
7
```
```
1
```
```
Returns: { }
```
If we should have only one component, we must paint the whole rectangle the same color. However, then the component won't be a tree.

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.