Black Square
Time limit1sMemory limit128 MB
Given one row of an m×n grid known to contain a black s×s square, determine if the square's position is unique, ambiguous, or impossible from that row alone.
- Level
Medium5 of 10
- Topics
- Implementation, Math, Simulation
- Solved
- No attempts yet
Problem
Inspired by Kazimir Malevich's masterpiece Black Square, Peter Palevich wants to create his own version. He prepared a rectangular grid of m × n white cells, arranged in m rows of n cells each.
Peter painted some cells black so that the black cells formed a solid square of size s × s. Later that day he grew unhappy with the result and destroyed it, cutting the grid into horizontal stripes of size 1 × n and burning them in the fireplace.
The next morning Peter changed his mind and decided to restore the painting. Searching the ashes, he found that exactly one stripe had survived: the k-th one counted from the top.
Given this single stripe, decide whether the original painting can be recovered.
Input
The first line contains four integers m, n, s, and k (1 ≤ m, n ≤ 5000; 1 ≤ s ≤ min(m, n); 1 ≤ k ≤ m).
The second line contains n characters describing the k-th row of the painting: . marks a white cell and * marks a black cell.
Output
Print Unique if the original painting can be reconstructed in exactly one way.
Print Ambiguous if two or more different paintings are consistent with the surviving stripe.
Print Impossible if no valid painting could have produced this stripe.