Lilypads | Topcoder Archive

Problem Statement

A pond has R*C lilypads, arranged into a rectangular grid with R rows and C columns. Both rows and columns are numbered starting from zero. A frog is sitting on the lilypad (r0,c0).

Help the frog visit each of the other lilypads exactly once. The frog can jump arbitrarily far, but only horizontally or vertically. Additionally, the frog cannot make two consecutive jumps in the same direction. (Switching to opposite direction is allowed.)

Return a int[] with 2*R*C elements: the coordinates of lilypads in the order in which the frog should jump. That is, if the first two jumps are (r0,c0) -> (r1,c1) -> (r2,c2), your return value should be { r0, c0, r1, c1, r2, c2, ... }. Any valid solution will be accepted.

Definition

Class:: Lilypads
Method:: traverse
Parameters:: int, int, int, int
Returns:: int[]
Method signature:: int[] traverse(int R, int C, int r0, int c0)
(be sure your method is public)

Notes

A solution always exists.

Constraints

R will be between 1 and 50, inclusive.
C will be between 1 and 50, inclusive.
r0 will be between 0 and R-1, inclusive.
c0 will be between 0 and C-1, inclusive.

Examples

```
1
```
```
3
```
```
0
```
```
1
```
```
Returns: {0, 1, 0, 0, 0, 2 }
```
Three lilypads in a row, the frog starts on the middle one. In our sample solution it jumps to the left one and then to the right one.
```
2
```
```
2
```
```
0
```
```
1
```
```
Returns: {0, 1, 0, 0, 1, 0, 1, 1 }
```
A 2x2 square of lilypads. Our frog visits them in counter-clockwise order.
```
3
```
```
3
```
```
1
```
```
2
```
```
Returns: {1, 2, 1, 0, 0, 0, 0, 2, 2, 2, 2, 0, 2, 1, 0, 1, 1, 1 }
```
In the figure below, digits 0 to 8 represent the nine lilypads in the order in which the frog visited them according to the example output. 273 180 564

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.