HCI '16 - BinaryBomb

View as PDF

Submit solution

Points: 17 (partial)
Time limit: 7.0s
Memory limit: 1G

Authors:
Problem types

An evil villain, Diamond Bomber, is attacking BinaryLand with bombs! Fortunately, of the 10 residents of BinaryLand, only one was killed and the other resident, Mr. B, managed to take shelter underground before the attack. When he emerged above ground, he found that BinaryLand was blown to bits (well, it was in bits before the attack but you get the idea).

It is your job as a member of the rescue team to code a program to work out the shortest path for Mr. B to take to get to the rescue zone from his shelter (he can only travel left, right, up or down). However, there are a few problems:

  1. You do not know what the current layout of BinaryLand is, but you know about the bombs that have exploded.

  2. There are three types of bombs:

    Type 1: Changes all values caught in bomb's radius to 1

    Type 2: Changes all values caught in bomb's radius to 0

    Type 3: FLIPS all values caught in bomb's radius (1 becomes 0, 0 becomes 1)

  3. The Diamond Bomber's bombs explode in a diamond pattern (surprise!)

    E.g. Bomb of Radius 2 Type 1

    000010000
    000111000
    001111100
    000111000
    000010000
  4. Distances in BinaryLand are calculated through binary, so the shortest path has the shortest distance when the path is converted from binary to a base 10 integer.

    E.g. If the path from the shelter to the rescue area is 0 \to 1 \to 0 \to 1, the binary number is 1010 (with the starting point as last digit) and the distance will be 10 after converting to a base 10 integer.

The fate of Mr. B lies in your hands, Good Luck!

Note: The default layout of BinaryLand is all 0s and all coordinates are 0-indexed. The value at the shelter and the rescue location must also be considered when working out the shortest path.

Input Specification

The first line of input has 3 integers: H, W, B (representing the height and width of BinaryLand, and the number of bombs respectively)

The next line of input has 4 integers: S_x, S_y, R_x, R_y (representing the coordinates of the shelter and the rescue area respectively)

The next B lines contain 4 integers each: B_T, B_x, B_y, B_R (representing the type of bomb, the coordinates of the centre of the bomb, and the bomb radius respectively)

Output Specification

A single integer stating the shortest distance from the shelter to the rescue area \bmod 13\,371\,337.

This is because numbers may become too large to fit in an integer or a long long.

Constraints

Subtask 1 [30%]

1 < H, W \le 100

1 < B \le 500

1 < B_R \le 50

Subtask 2 [70%]

1 < H, W, B \le 1\,000

1 < B_R \le 100

Subtask 3 [0%]

Sample test cases.

Sample Input 1

5 5 2
0 0 4 4
1 2 2 2
2 2 2 1

Sample Output 1

68

Explanation

After the bombs exploded, this is the layout of BinaryLand:

00100
01010
10001
01010
00100

The shortest distance from shelter (0, 0) to rescue zone (4, 4) is through (shelter) 0 \to 0 \to 1 \to 0 \to 0 \to 0 \to 1 \to 0 \to 0 (rescue). The binary number is 001000100, which converts to 68.

Sample Input 2

25 25 5
3 8 24 24
1 15 17 6
3 6 24 4
3 23 11 7
2 18 20 4
1 22 17 5

Sample Output 2

0

Comments

There are no comments at the moment.