Line Sweep

View as PDF

Submit solution

Points: 25
Time limit: 1.0s
Memory limit: 256M

Author:
Problem type

Preoccupied with coding, you've allowed your room to become quite dusty. You'd better sweep it before your parents find out!

Your room can be represented by a two-dimensional grid of cells, with N rows and M columns. Each cell either contains a piece of furniture, or is empty and must be swept. At least one cell is empty.

To get the job done, you'll be using a broom, of course - in particular, a linear broom. A linear broom of length X can cover a vertical line of X consecutive cells. One sweep of the broom consists of placing it down, and then moving it horizontally by any distance. However, at all times during a sweep, the broom must remain entirely within the boundaries of the room, and all X of the cells it covers must be empty. All of the cells that the broom moves over during a sweep are then rid of dust.

The bigger the better, so you'd like to purchase a broom of the largest size possible such that it's possible to sweep your entire room with it. Your room is completely swept once every empty cell has been involved in at least one sweep of the broom. After deciding on the size of your broom, you'd also like to minimize the number of sweeps required to get the job done.

Input Specification

The first line of input contains three integers N M and F, which are the number of rows, columns and pieces of furniture respectively (1 \le N \le 2\,000; 1 \le M \le 2\,000; 1 \le F < NM).

The next F lines contain values r c (1 \le r \le N, 1 \le c \le M) which is the row and column position of one piece of furniture. No two pieces of furniture will be at the same coordinates.

Output Specification

The output is composed of two numbers.

The first line contains the integer width of the largest broom that can be purchased. The second line contains the number of sweeps required to sweep all empty cells.

Sample Input

5 7 2
3 4
5 7

Output for Sample Input

2
4
Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported

Comments


  • 1
    sunnylancoder  commented on April 9, 2017, 3:13 a.m.

    Is 0 a valid distance to move? (The broom sweeps only one thing)