Count the 4-connected white regions of a binary sky given only its N by N averaged and rounded-down picture.
Medium7GreedyPrefix sumBFSNo attempts yetTime limit1sMemory limit256 MBThe 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 N×N square centred on that position, rounded down to an integer. N is odd, so the square has exactly one centre. The average always divides by N2, 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 (N−1)/2 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.
The first line has three integers N, R and C (1≤N≤99, N is odd, N≤R,C≤1000): 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 R lines has C hexadecimal numbers Lr,c separated by one space. Every value is written with four uppercase hexadecimal digits and runs from 0000 (black) to FFFF (white). Lr,c is the reported brightness of the pixel in row r and column c.
The given picture is always the blur of some sky that meets the rules above.
Print one integer, the number of stellar bodies visible in the picture.