Telescope
Time limit1sMemory limit256 MB
Count the 4-connected white regions of a binary sky given only its N by N averaged and rounded-down picture.
- Level
Medium7 of 10
- Topics
- Greedy, Prefix sum, BFS
- Solved
- No attempts yet
Problem
The space telescope Inquisition IV was launched more than ten years ago, and the pictures it sends back are blurry. Each pixel of a picture is the average of the true pixels in the square centred on that position, rounded down to an integer. is odd, so the square has exactly one centre. The average always divides by , and a position of the square that falls outside the captured region counts as a black pixel.
The sky itself is simple. Every stellar body is a group of pixels of full brightness FFFF joined horizontally and vertically, and every other true pixel is fully black 0000. The telescope framed the whole scene, so no blur from a stellar body falls outside the picture. A pixel of brightness FFFF is therefore never within rows or columns of the top, bottom, left or right border of the picture.
Read the blurred picture and count the stellar bodies in it.
Input
The first line has three integers , and (, is odd, ): the side of the blur square, the number of rows of the picture and the number of columns of the picture.
Each of the next lines has hexadecimal numbers separated by one space. Every value is written with four uppercase hexadecimal digits and runs from 0000 (black) to FFFF (white). is the reported brightness of the pixel in row and column .
The given picture is always the blur of some sky that meets the rules above.
Output
Print one integer, the number of stellar bodies visible in the picture.