SimpleMaze | Topcoder Archive

Problem Statement

An infinite board divided into a grid of unit square cells is called a simple maze if it has the following properties:

Each cell is either empty ('.') or contains an obstacle ('#').
The number of empty cells is finite.
All empty cells form one 4-connected component (explained below).
All obstacles form one 4-connected component.

When in the maze, you can move from an empty cell into any other empty cell that shares a side with your current empty cell. Property #3 means that you can walk from any empty cell into any other empty cell in the maze. Property #4 means that all the obstacles are connected in the same way. (If all obstacles were changed into empty cells and vice versa, it would also be possible to walk between any two empty cells.)

We can describe a simple maze by describing the boundary between the empty cells and obstacles. You are given this description in the int[] moves. Use the following pseudocode to construct the boundary:

Take a pen and place it anywhere onto the infinite plane.
For each i from 0 to length(moves)-1:
    If i is even:
        Move the pen moves[i] steps to the right.
    Else:
        Move the pen moves[i] steps upwards.

Note that some elements of moves will be negative. These correspond to movement to the left or downwards, respectively. For example, if moves = {3, 1, -2, 2, -1, -3} then the maze will look as follows:

#####
#.###
#.###
#...#
#####

(All other cells in the infinite plane are obstacles. We started drawing the boundary from the bottom left corner of the empty area.)

It is guaranteed that moves will always describe a closed polyline that never touches or intersects itself.

The distance between two empty cells is the smallest number of steps needed to get from one of the cells into the other.

You are given the int[] moves. For each pair of empty cells in the maze, compute their distance. Let S be the sum of those distances. Compute and return the value S modulo (10^9 + 7).

Definition

Class:: SimpleMaze
Method:: findSum
Parameters:: int[]
Returns:: int
Method signature:: int findSum(int[] moves)
(be sure your method is public)

Constraints

moves will contain between 4 and 2,000 elements, inclusive.
moves will contain an even number of elements.
For each valid i, 1 <= |moves[i]| <= 1,000,000.
moves will describe a closed polyline that never touches or intersects itself.

Examples

{1,1,1,1,-1,1,-1,-1,-1,-1,1,-1}

Returns: 16

The maze looks like this: #.# ... #.#

```
{10,10,-10,-10}
```
```
Returns: 33000
```
The empty space is an empty square with side length 10.

{1,3,1,-3,2,1,1,-1,1,2,-2,1,2,1,-6,-4}

Returns: 629

...... .#..## .#.... .#..#.

{3,1,-2,1,1,1,-1,1,1,1,1,1,-3,-6}

Returns: 237

... ..# .## ..# .## ...

```
{-2,-2,-1,-3,-1,1,-1,2,-1,2,-2,-2,-1,-2,-1,-1,-1,3,-1,2,-9,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,2,-1,1,-2,-4,9,-3,-7,-6,-1,-3,2,2,1,2,1,1,1,1,1,-1,1,-1,1,-5,-1,-1,-1,-1,-1,3,1,3,-1,-1,-1,-3,-1,-1,-1,-1,-2,1,-1,2,-1,3,1,2,1,4,-2,9,1,1,2,-1,1,-2,1,1,1,1,1,1,1,1,1,5,-2,1,-2,1,-2,1,-3,2,3,1,3,2,-3,1,-3,2,3,1,2,1,2,1,3}
```
```
Returns: 516034
```
############################################# ####...######.........##########..####..##### ##.......####...####...#########..####..##### #...###.........####...#########..####..##### #...#########...###...#########....##....#### ##....#######...#...###########....##....#### ###.....#####...##...#########..#..##..#..### ######...####...###...########..##....##..### #...###...###...####...######...##....##...## ##.......####...#####...#####..####..####..## ###.....#####...######.........####..####..## #############################################

{1000000,1000000,-1000000,-1000000}

Returns: 333218986

Don't forget mod.

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.