oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

boundlessboxes Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

boundlessboxes.html

Task

Several months ago, Peer was painting triangles on a canvas from the outside in. Now that triangles are out and squares are in, his newest paintings use concentric squares, and are created from the inside out! Peer starts painting on a rectangular canvas divided into a perfect square grid. He selects a number of single grid cells to act as central seeds, and paints them with the darkest shade. From each of the seed squares, Peer paints a larger square using a lighter shade to enclose it, and repeats with larger squares to enclose those, until the entire canvas is covered. Each square is exactly one grid cell larger and one shade lighter than the one it encloses. When squares overlap, the grid cell is always filled using the darker shade.

Input

Each test case begins with a single line containing three integers, m, n, and s, separated by spaces. The canvas contains exactly m x n grid cells (1 ≤ m, n ≤ 1,000), numbered 1, . . . ,m vertically and 1, . . . , n horizontally. Peer starts the painting with s (1 ≤ s ≤ 1,000) seed cells, described on the following s lines of text, each with two integers, ri and ci (1 ≤ ri ≤ m, 1 ≤ ci ≤ n), describing the respective grid row and column of each seed square. All seed squares are within the bounds of the canvas.

For example, the input for the test case shown in the figure above, would look like:

10 8 3
3 3
7 7
10 2

Output

For each test case, your program should print one integer on a single line: the number of different shades required for the painting described.

Output corresponding to the sample input would appear as such:

6

boxes.jpg

Tags

Graph Theory

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
1100111s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o boundlessboxes -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.