UVa 10703

From Algorithmist
Jump to navigation Jump to search

10703 - Free Spots[edit]

Summary[edit]

A straight forward problem where doing the first thing that comes to mind will work.

Explanation[edit]

We are given a w by h board of initially free spots. We are also given subrectanges of taken spots. We want to determine the number of spots which are not covered by a taken subrectange. The limits on the problem make it very easy. Start with an initially empty board. For each subrectangle, mark every cell in the subrectangle as taken. After all subrectanges are taken, count the free spots in a single iteration over the board.

Implementations[edit]

Input[edit]

1 1 1
1 1 1 1

2 2 2
1 1 1 2
1 1 2 1

493 182 3
349 148 363 146
241 123 443 147
303 124 293 17

0 0 0


Output[edit]

There is no empty spots.
There is one empty spot.
There are 83470 empty spots.