http://wangsc.ga/posts/20170224-interview-char-rec/
Character recognition is the conversion of images into text. For now we consider each character in the picture is a N*M matrix with only zeros and ones, and we need to recognize K characters. You are to write a program to find minimal number of pixels so that we can recognize each character.
For example, we have only two characters
T
and L
, and the matrix size is 3*3
, we can think T
and L
are
So we can recognize the character with only botton-left pixel, the anwser is 1;
Limits
- Memory limit per test: 256 megabytes
- Time limit per test: The faster the better
Compile & Environment
C++
Java
Input
The first line of input is three integers
Which represents the size of matrix and number of characters. Then is following
N
, M
, K
(1 <= N, M <=10
, 2 <= K <= 6
).Which represents the size of matrix and number of characters. Then is following
K
blocks, which represents the matrix. Notice that each block starts with a blank lineOutput
You should output the minimum number of pixels, which is the anwser.
Test Case
Generalize problem
Given
K
bit serie with same length (N*M
), find the minimum bits required to distinguish them.