|Task 4 - Bitmap|
Components of a Bitmap
Black and white pictures are usually stored as bitmaps. A bitmap is a rectangular grid of pixels.
A polyline between pixels P and Q is a sequence of black pixels P=P1, P2, …, Pk=Q, where Pi and Pi+1 (i=1, …, k-1) are (vertically or horizontally) adjacent pixels. A polyline P1, P2, ..., Pk is closed if P1=Pk, and Pi <> Pj (i=1, …, k-1, j=2, …, k) for i<j unless i=1 and j=k (that is the polyline does not contain the same pixel twice).
A set of black pixels S is connected if for each pair of pixels (P,Q) in S there is at least one polyline L between P and Q with all pixels of L belonging to S.
A component of a bitmap is a maximal connected set of black pixels. A component may enclose holes. A hole consists of white pixels that are inside a closed polyline. A compact component encloses no holes.
Note that in Figure 1 the white pixel in the middle, marked with x, is not inside the highlighted closed polyline.
Figure 2 shows a bitmap with five components, of which two are compact ones.
You are to write a program that computes the total number of components and the number of compact components of a given coded bitmap.
Encoding. The bitmaps under investigation are coded (compressed) with the following method. Each row is coded with a sequence of integers W1, B1, ..., Wk, Bk, where Wi is the number of consecutive white pixels, and Bi is the number of consecutive black pixels, respectively.
For example, the code of the first line of the bitmap in Figure 2 is the sequence 4 7 4 4 1 0. Components 4 and 5 are compact, while components 1, 2 and 3 are not compact.
The first line of the file bitmap.in contains two positive integers, N and M. N (2<=N<=10000) is the number of rows and M (2<=M<=1000) is the number of columns of the bitmap. The next N lines contain the coded bitmap according to the paragraph on encoding. Each line terminates with -1.
The file bitmap.out must contain two lines, with a single integer in each line. The first line contains the number of all components and the second line contains the number of compact components of the input bitmap.
EXAMPLE INPUT AND OUTPUT
If the first line of your output file contains the correct number of all components, then you obtain 50% of the scores. If the second line of your output file contains the correct number of compact components, then you obtain an additional 50% of the scores.