ClickOnAll | Topcoder Archive

Problem Statement

The clicking game is played on a rectangular grid that has R rows by C columns. Both rows and columns are numbered starting from 0. Cell in row r and column c will be denoted (r, c).

Two cells are called neighbors if they are adjacent horizontally, vertically, or diagonally. (I.e., neighbors are cells that share a side or a corner.)

The goal in the clicking game is to click on each cell of the grid exactly once. Your first click can be on any cell you like. In each of the following clicks you are not allowed to click any of the neighbors of the last cell you clicked.

Find any valid sequence of clicks. If the sequence of clicked cells is (r0, c0), (r1, c1), (r2, c2), ..., you should return the following int[]: {r0, c0, r1, c1, r2, c2, ...}. Any valid solution will be accepted. If there is no valid solution, return an empty int[] instead.

Definition

Class:: ClickOnAll
Method:: click
Parameters:: int, int
Returns:: int[]
Method signature:: int[] click(int R, int C)
(be sure your method is public)

Notes

If a solution exists, each correct return value will contain exactly 2*R*C numbers.

Constraints

R will be between 1 and 30, inclusive.
C will be between 1 and 30, inclusive.

Examples

```
4
```
```
5
```
```
Returns: {0, 4, 1, 2, 3, 2, 1, 4, 2, 0, 0, 1, 3, 4, 3, 0, 1, 3, 0, 0, 0, 3, 2, 4, 2, 1, 0, 2, 2, 2, 1, 0, 2, 3, 3, 1, 3, 3, 1, 1 }
```
In the figure below the cells of the grid are numbered 0 through 19 in the order in which we should click on them. This sequence of clicking corresponds to the example output. +----+----+----+----+----+ | 9 | 5 | 13 | 10 | 0 | +----+----+----+----+----+ | 15 | 19 | 1 | 8 | 3 | +----+----+----+----+----+ | 4 | 12 | 14 | 16 | 11 | +----+----+----+----+----+ | 7 | 17 | 2 | 18 | 6 | +----+----+----+----+----+
```
2
```
```
2
```
```
Returns: { }
```
Regardless of where you click first, you will not be able to make the second click: all three remaining cells are neighbors of the one you clicked first. Thus, there is no solution.
```
1
```
```
7
```
```
Returns: {0, 2, 0, 0, 0, 5, 0, 1, 0, 4, 0, 6, 0, 3 }
```
Order of clicking described in the example output: +----+----+----+----+----+----+----+ | 1 | 3 | 0 | 6 | 4 | 2 | 5 | +----+----+----+----+----+----+----+
```
7
```
```
1
```
```
Returns: {2, 0, 0, 0, 5, 0, 1, 0, 4, 0, 6, 0, 3, 0 }
```
This is essentially the same solution as in the previous example, but this time we have all cells in the same column instead of having them in the same row.

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.