Image Square Lengths
Time limit1sMemory limit128 MB
Given a grid showing the topmost color at each pixel from K sequentially drawn axis-aligned squares, determine for each color the minimum and maximum possible side length consistent with the final image.
- Level
Hard8 of 10
- Topics
- Matrix, Greedy, Implementation, Simulation
- Solved
- No attempts yet
Problem
Mirko was bored during computer class, so he opened Paint and created an N x N pixel image.
Because he had not paid attention while the teacher explained the tool, Mirko only knows how to draw filled squares in different colors. He first drew one square of color 1, then one square of color 2, and so on through color K. A later square may cover part of an earlier square.
After the teacher noticed the drawing, she could reconstruct the order in which the colors were drawn, but not the original side lengths of the squares.
For each color A, the possible side lengths form an integer interval [a, b]: every length x with a <= x <= b could have been the side length of the square of color A in some drawing that produces the final image.
Write a program that finds this largest interval for every color.
Input
The first line contains two integers N and K (1 <= N <= 1000, 1 <= K <= 9): the side length of the image and the number of squares Mirko drew.
Each of the next N lines contains N characters. Each character is either . or one of the digits from 1 to K. A . means no square ever covered that pixel. A digit x means the last square to cover that pixel had color x.
Output
Print K lines. On line i, print two integers: the smallest and largest possible side length of the square of color i.