WolfInDarkRoom | Topcoder Archive

Problem Statement

Wolf Sothe is now in his room, but the lights in the room are turned off. Sothe wants to turn on the lights, but he has lost the controller of the lights.

Sothe's room can be regarded as a grid of square cells with N rows and M columns. The top left cell of the grid has coordinates (0,0) and the bottom right cell has coordinates (N-1,M-1). He is now at (r,c), facing down.

Sothe will find the controller by repeating these steps in an infinite loop (at first, variable k is equal to 1):

Move k cells forward, visiting all cells along the way (including the cell you finish on). If it's impossible to go forward anymore, stop and move on to the next step.
Turn right.
Increment k by 1.

You're given 4 ints N, M, r and c. Compute and return the number of cells that Sothe can visit by repeating the decribed steps. Even if a cell is visited several times, you should only count it once.

Definition

Class:: WolfInDarkRoom
Method:: count
Parameters:: int, int, int, int
Returns:: int
Method signature:: int count(int N, int M, int r, int c)
(be sure your method is public)

Constraints

N will be between 1 and 50, inclusive.
M will be between 1 and 50, inclusive.
r will be between 0 and N-1, inclusive.
c will be between 0 and M-1, inclusive.

Examples

```
3
```
```
3
```
```
0
```
```
0
```
```
Returns: 8
```
At first, Sothe is at (0,0). He moves down to (1,0) and turns right (so his general direction is left). Now, he faces a wall, so he doesn't move at all. He turns right again and moves back to (0,0); even though k=3, he can't move further, because there's a wall in his path. Then, he moves along cells (0,1), (0,2), (1,2), (2,2), (2,1), (2,0), (1,0), (0,0), (0,1), ... Sothe can't reach (1,1) at all.
```
3
```
```
3
```
```
0
```
```
2
```
```
Returns: 9
```
Sothe will reach any cell. The first few cells on his path are (0,2), (1,2), (1,1), (1,0), (0,0), (0,1), ...
```
10
```
```
4
```
```
2
```
```
3
```
```
Returns: 30
```
```
30
```
```
18
```
```
17
```
```
11
```
```
Returns: 292
```
```
50
```
```
50
```
```
25
```
```
25
```
```
Returns: 1372
```
```
49
```
```
40
```
```
20
```
```
2
```
```
Returns: 793
```

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.