VisitN | Topcoder Archive

Problem Statement

You are on a 30x30 chessboard. The rows of the chessboard are numbered 0 through 29 from the north to the south. The columns of the chessboard are numbered 0 through 29 from the west to the east. Your starting cell is (r,c).

Your task is to visit exactly n cells of the chessboard (including the one where you start). You can move in steps. In each step you can move one cell in one of the four cardinal directions: north, south, east, or west. We will denote these movements 'N', 'S', 'E', and 'W'. You may visit the same cell multiple times. You may not leave the chessboard. (E.g., if you are in row 0, you cannot move north.)

Return a String with at most 2000 characters: any sequence of moves that never leaves the chessboard and visits exactly n distinct cells.

Definition

Class:: VisitN
Method:: visit
Parameters:: int, int, int
Returns:: String
Method signature:: String visit(int n, int r, int c)
(be sure your method is public)

Constraints

n will be between 1 and 900, inclusive.
r will be between 0 and 29, inclusive.
c will be between 0 and 29, inclusive.

Examples

```
1
```
```
4
```
```
7
```
```
Returns: ""
```
The only way to visit exactly one cell is to make no steps at all.
```
2
```
```
4
```
```
7
```
```
Returns: "N"
```
By taking a step north we have visited two cells: the cell (4,7) where we started and the cell (3,7) we just reached.
```
2
```
```
0
```
```
17
```
```
Returns: "W"
```
This time we are on the north end of the chessboard, so we cannot take a step north. Other valid solutions include "E", "S", and "SNSNSNS".
```
4
```
```
1
```
```
1
```
```
Returns: "NWEE"
```
Note that this path visits the cell (0,1) twice, so the number of distinct cells it visits is 4, not 5.
```
10
```
```
5
```
```
13
```
```
Returns: "NWSSEENNSSWS"
```

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.