The Robot Plow

Interview

Time limit1sMemory limit128 MB

Summary

Given up to 200 axis-aligned rectangles on a grid at most 240 by 240, count the number of unit squares covered by at least one rectangle.

Level: Easy3 of 10
Topics: Implementation, Simulation, Array, Brute force
Solved: No attempts yet

Problem

Farmer John has purchased a new robotic plow to relieve himself from the drudgery of plowing field after field after field. The plow does the job, but with one restriction: it can only plow a perfect rectangle whose sides have integer length.

Because FJ's field has trees and other obstacles, he programs the plow to plow many different rectangles, which may overlap. He is curious how many squares of his field are actually plowed after all of the instructions run. Each instruction describes a rectangle by giving the $x$ , $y$ coordinates of its lower-left and upper-right corners.

The field is partitioned into squares whose sides are parallel to the $x$ and $y$ axes. The field is $X$ squares wide and $Y$ squares high ( $1 \le X \le 240$ ; $1 \le Y \le 240$ ). Each of the $I$ instructions ( $1 \le I \le 200$ ) consists of four integers $X_{ll}$ , $Y_{ll}$ , $X_{ur}$ , $Y_{ur}$ ( $1 \le X_{ll} \le X_{ur} \le X$ ; $1 \le Y_{ll} \le Y_{ur} \le Y$ ), the lower-left and upper-right coordinates of the rectangle to plow. The plow plows every square in the range $(X_{ll} \dots X_{ur},\ Y_{ll} \dots Y_{ur})$ , inclusive of both endpoint columns and rows.

Consider a field that is 6 squares wide and 4 squares high. As FJ issues a pair of plowing instructions (shown), the field gets plowed as shown by '*' and '#' (already-plowed squares all look the same, but '#' marks the most recently plowed ones):

    ......             **....             #####.
    ......  (1,1)(2,4) **....  (1,3)(5,4) #####.
    ......             **....             **....
    ......             **....             **....

A total of 14 squares are plowed.

Input

Line 1: Three space-separated integers: $X$ , $Y$ , and $I$
Lines 2..I+1: Line $i+1$ contains plowing instruction $i$ , described by four integers: $X_{ll}$ , $Y_{ll}$ , $X_{ur}$ , $Y_{ur}$

Output

Line 1: A single integer, the total number of squares plowed

Examples3

Example 1
Input
```
6 4 2
1 1 2 4
1 3 5 4
```
Expected output
```
14
```
Example 2
Input
```
1 1 1
1 1 1 1
```
Expected output
```
1
```
Example 3
Input
```
10 10 2
1 1 2 2
5 5 6 6
```
Expected output
```
8
```