Dark islands
A photographer wants to understand the shadows in a picture. They choose a brightness threshold t and count as dark all pixels with brightness at most t. Dark pixels adjacent by a side form islands. At threshold 0 there are few islands, only the blackest points. As the threshold grows there is more dark, islands appear and merge, and at threshold 255 the whole picture is one island. Count the islands for every threshold from 0 to 255.
Three tests are photographs by the site's author, 120 pixels wide. The brightness of a pixel in them is (299·R + 587·G + 114·B + 500) div 1000, integer luma by the Rec. 601 standard.
Input
The first line holds the height h and width w of the picture (1 ≤ h·w ≤ 100,000). Then h lines of w integers from 0 to 255, the brightness of the pixels.
Output
One line of 256 numbers separated by spaces: the number of islands at thresholds 0, 1, …, 255. Pixels are neighbours if they share a side; diagonal pixels are not neighbours.
Examples
Example 1
4 5 9 9 1 9 9 9 3 2 3 9 9 9 9 9 9 0 9 4 9 0
2 3 3 3 4 4 4 4 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Example 2
3 3 0 5 0 5 0 5 0 5 0
5 5 5 5 5 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 11 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Counting the islands for one threshold is easy, with breadth-first or depth-first search. But there are 256 thresholds, and each traversal goes over the whole picture. How does the picture at threshold t + 1 differ from the one at t?
2Hint 2
On going to threshold t + 1, dark pixels do not disappear; new ones are added, exactly those with brightness t + 1. Islands are only born and merge. Which structure keeps track of such merges?
3The idea
Go through the thresholds in increasing order and add pixels to a disjoint set union. A new dark pixel is a new island: the counter goes up by one. Then it is merged with each dark neighbour, and each successful merge is one island fewer. After all the pixels of a given brightness, the counter is the answer for that threshold.
4Walkthrough
First distribute the pixels by brightness into 256 lists, a counting sort in O(h·w). Pixel (r, c) is element r·w + c; its neighbours above and below are w away, left and right one away, if they do not go past the edge of the row. The array dark marks which pixels are already dark: a new pixel may be merged only with those.
The order of addition within one brightness does not matter: by the end of its processing all pixels of this brightness have been added, and the islands are the same as with an honest traversal. Note that new pixels of the same brightness can also merge with each other; their neighbour check takes this into account, since dark is set before the check.
The function measure.label in scikit-image and the Hoshen–Kopelman algorithm from percolation physics work the same way, only they need one threshold, and we need all of them at once, which disjoint set union gives in one pass.
4+Solution
5Complexity
Each pixel is added once and tries at most four merges: O(N α(N)) for N = h·w pixels, plus 256 for the output. A traversal for each threshold is O(256·N).
6Common mistakes
- A traversal anew for each threshold. The answers are right, but on a picture of 90,000 pixels it is 23 million traversal steps, which will not fit in the sixth test.
- Neighbours across the edge of a row. Pixels r·w + w − 1 and (r + 1)·w are neighbours in the array but not in the picture: the right edge of one row and the left edge of the next.
- Diagonal neighbours. In the second sample the dark cells with brightness 0 touch only at corners, and at thresholds from 0 to 4 they are five separate islands.
- Recursion. The last test has one winding island of 45 thousand pixels. A recursive depth-first search hits the depth limit, and so does a recursive
findwithout union by size, if the tree has time to stretch out.