IMGREC2 - Digital Image Recognition

Description

According to Wikipedia, image processing is any form of signal processing for which the input is an image, such as photographs or frames of video; the output of image processing can be either an image or a set of characteristics or parameters related to the image. Most image-processing techniques involve treating the image as a two-dimensional signal and applying standard signal-processing techniques to it.

The task you are facing here is a relatively easy one (compared to our general conception of image processing!). Given a black-and-white image of size R * C with some digits (and possibly other shapes) on it, your program needs to figure out the digits written on the image. Specifically, the digits drawn on the graph will adhere to the following rules:

1) Digits are drawn with a series of strokes. A stroke can be regarded as a rectangle of any size on the image, and its edges will always be parallel to either x-axis or y-axis. The number of strokes required to draw each digit will be exactly as follows:

0 	1 	2 	3 	4 	5 	6 	7 	8 	9
4 	1 	5 	4 	3 	5 	5 	2 	5 	5

Refer to the figure below if you are unclear about how the digits are drawn.

2) Although the width of strokes used to draw a digit might be different, the outer shapes of digits will strictly follow those specified in the figure below.

3) In order for a digit to be recognizable, all parts (strokes and joints) presented in the graph below must also be clearly distinguishable in the image.

(Refer to the last sample test case if you are unsure about this requirement; in that test case, when the middle stroke of 2 is omitted, the number should not be considered as recognizable.)

4) You may assume that the image is not rotated, and there is no noise in the input.

Please output the sum of digits recognizable in the graph. In the case that no characters is recognizable, please output 0 instead.

Input

There are multiple test cases in the input file.

Each test case starts with two integers, R and C (1 <= R,C <= 500), specifying the number of rows / columns of the graph. Each of the following R lines contains consecutive C characters ("0" or "1"), describing the image to be processed.

Two successive test cases are separated by a blank line. A case with R = 0, C = 0 indicates the end of the input file, and should not be processed by your program.

Output

For each test case, please print a single integer, the sum of recognizable numbers. See the sample output for format details.

Example

Input:
5 12
001101011111
000101000011
000101001111
001101000011
000000000111

5 3
111
010
110
010
110

6 14
11111000011111
11001000000011
11111001000000
11111001001110
11001011001010
11111000001110

5 2
11
01
11
01
11

6 9
111100111
000100001
000100011
011100010
010000011
011110000

0 0

Output:
Case #1: 4
Case #2: 0
Case #3: 15
Case #4: 3
Case #5: 2

Added by:Fudan University Problem Setters
Date:2008-11-15
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: C99 ERL JS-RHINO NODEJS PERL6 VB.NET
Resource:ACM/ICPC Asian Regional Contest, Hangzhou 2008

hide comments
2014-05-18 23:25:21 Encho
@Water u doin, Read the following carefully "In order for a digit to be recognizable, all parts (strokes and joints) presented in the graph below must also be clearly distinguishable in the image." In the second "2" in last sample the middle stroke is not clearly distinguishable as if you remove the vertices, it would have length 0, i.e. it doesn't exist as a stroke.
2014-05-07 21:14:37 Saša Vučković
Why isn't the answer in the 5th case 4? I can see two 2s.
2014-05-03 01:43:03 Encho
djokan, my AC program prints 8 on that test sample.
2014-05-03 00:06:44 djokan
What is the answer of this test case 4 or 8?

00010000001
00010100101
00010100101
00010111101
00010000101
00010000101
00010000001
00011111111
00000000001
00000000001
00000000001
2014-05-02 02:38:31 Encho
Is this a valid '7' ?
00000
00110
01110
00000

Edit : Got AC and my program assumed the above case is invalid '7'.

Last edit: 2014-05-03 13:21:26
2010-06-10 07:26:59 :D
Is this a valid '7'?
5 5
11110
11111
00011
00011
00011

Is this a valid '4'?
5 5
11000
11000
11111
00001
00001

Re: Nevermind, already got AC. Both are invalid.

Last edit: 2010-06-15 11:34:21
2010-02-23 14:50:03 [Rampage] Blue.Mary
The answer should be 2.
2010-01-31 22:34:34 jcl
Are diagonal adjacencies considered "clearly distinguishable"? This is not covered in the problem description or test cases. For example, is the value of the following test case zero or two?

2 2
10
01
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.