410081: GYM103938 I Moldy Sandwich

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Moldy Sandwichtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

We're a student org created by transfer students, for transfer students. We know firsthand how tough it can be to find your way and your people after transferring into the CS major or into UT more generally. If you're an internal transfer, external transfer, or ATP student we hope to see you!

The CS Transfer Society is hosting a scavenger hunt in the GDC! At the time of writing this I have no idea what the objectives are, so I'll assume that the goal is to collect as many moldy sandwiches as possible!

The GDC can be (grossly) represented by an $$$N$$$ by $$$N$$$ grid. The CS Transfer Society has placed $$$M$$$ moldy sandwiches inside the GDC, marked by '#'. All other locations are marked as '.'.

You are participating on behalf of your CS week organization and, of course, are looking to win! However, time is running out. You know that with $$$K$$$ time you can explore any $$$K$$$ by $$$K$$$ square and collect all the moldy sandwiches in that square. (All squares have sides parallel to the sides of the original square).

You would like to know: for each $$$1 \le i \le M$$$, what value of $$$K$$$ is required to collect $$$i$$$ sandwiches, if you choose to explore the optimal $$$K$$$ by $$$K$$$ square?

Input

The first line contains a single integer $$$N$$$ ($$$1 \le N \le 10^3$$$), the side length of the square representing the GDC.

The next $$$N$$$ lines of $$$N$$$ characters each represent the current layout of the GDC, where '#' marks a moldy sandwich and '.' is filled in otherwise. It is guaranteed that the number of moldy sandwiches $$$M$$$ will be at least $$$1$$$ and will not exceed $$$100$$$.

Output

Print out $$$M$$$ integers in a single line: the minimum time needed to collect $$$i$$$ sandwiches for all $$$1 \le i \le M$$$.

ExampleInput
4
..#.
.#..
...#
....
Output
1 2 3 

加入题单

算法标签: