ManhattanSnowPlow | Topcoder Archive

Problem Statement

Manhattan is a grid of R west-to-east going streets crossing C north-to-south going avenues. There are R*C crossroads, with coordinates (0, 0) in the northwest corner to (R-1, C-1) in the southeast corner.

After heavy snowfall all segments of streets and avenues need to be plowed.

We only have a single snow plow. You can choose any of the crossroads as its starting location.

The snow plow can be programmed by entering a sequence of letters from the set NSEW (north, south, east, west). Each letter corresponds to movement to the next crossroad in that direction: 'N' decreases row, 'S' increases row, 'W' decreases column, and 'E' increases column.

You are given the dimensions R and C of Manhattan. Find one shortest possible program such that a snow plow with that program and a suitably chosen starting location plows the whole road network in Manhattan. Return the program. All programs with the shortest possible length will be accepted.

Definition

Class:: ManhattanSnowPlow
Method:: plow
Parameters:: int, int
Returns:: String
Method signature:: String plow(int R, int C)
(be sure your method is public)

Notes

You do not have to return the starting location, as it is implicitly determined by your program.
The snow plow may finish anywhere in Manhattan. In particular, it does not have to return to its starting location.

Constraints

R will be between 2 and 50, inclusive.
C will be between 2 and 50, inclusive.

Examples

```
2
```
```
2
```
```
Returns: "ENWS"
```
Manhattan looks as follows: +---+ | | +---+ The snow plow with our program starts in the bottom left (southwest) corner.
```
2
```
```
3
```
```
Returns: "ENWSWNE"
```
Manhattan looks as follows: +---+---+ | | | +---+---+ The snow plow with our program starts in the middle of the bottom (south) side.
```
4
```
```
4
```
```
Returns: "WNNSENWNEEESWNWSESWSEENNSWS"
```
In this test case Manhattan consists of 16 crossroads and 24 unit length segments between them. However, there is no snow plow program of length 24 that would clear the entire city. The shortest valid programs have 27 instructions. By the pigeon-hole principle, the snow plow will pass some street segment more than once.

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.