umsh1ume's blog

Please help for this problem
By umsh1ume, history, 8 years ago, In English

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. The first line of input is three integers 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 line. K is number of character matrices You should output the minimum number of pixels, which is the answer Input 2 3 2 111 010 100 100 output 1

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Basically, the question asks for the smallest set of grid positions such that for any i, j (1 <= i, j <= k), the ith and jth grid differ from each other in at least one of the chosen position. In the sample provided you can select the lower-left point, which is enough to distinguish between both grids.

I would solve this using bitmask dynamic programming. We have C(k, 2) pairs, which has value at most C(6, 2) = 15. We have to satisfy C(k, 2) conditions, each condition is whether some particular pair of grids have at least 1 differing position included in the set or not.

Let dp(i, mask) denote the minimum size of the set of cells you need to select from position i onwards such that 'mask' denotes the pairs already taken care of. The final answer is given by dp(0, 0).

You consider two cases, first is when you ignore the current cell and move on, and the second in which you decide to include the current cell in the set. In the latter case, for each pair (a, b) such that the ath and bth grids differ in this cell, set the corresponding bit in mask to be 1. This will give you the updated bitmask new_mask.

The recurrence is dp(i, mask) = min(dp(i+1, mask), 1+dp(i+1, new_mask)).

Time complexity = number_of_cells * 2^(number of pairs of grids) * (number of pairs of grids)
Given the above constraints, worst case comes out to be 10*10 * 2^15 * 15, which is around 5e7.

→ Reply