5.4.3 Character Recognition 字符识别
题目描述:
这个问题需要你写一个程序完成字符识别的任务.
每个完整的字符图案有 20 行,20 位.每个位是“0”或“1”.图 1a 对应着输入文件中的符号图案.
包括了 27 个字符图案的信息,以这样的顺序记录:
_abcdefghijklmnopqrstuvwxyz
其中 _ 表示空格字符.每个完整字符长 20 行.
输入文件包含一个或多个可能损坏的字符图案.一个字符图案可能以这些方式被损坏.
最多有一行被可能被复制了（就接在原来那一行的下面）
最多有一行可能丢失了
有些“0”可能被改成“1” 有些“1”可能被改成“0”
不会有任何一个字符图案既多余了一行并且又丢失了一行.在测试数据的任何一个字符图案 中,“0”和“1”的被改变率不超过 30%.
被复制的那一行中,原来的行和多余的行可能都损坏了,而且损坏的部分可能并不相同.
写一个程序,使用 font.in 提供的字体,在输入文件提供的图象中识别出一个或多个的字符序列.
使用提供的字体图象来识别字符的时候,要找出最佳的多余行或遗漏行,使找出的所有“0”和
“1”的变化数量最小.在所有可能的多余行中,只按损坏数据最少的那一行计算.你必须确定和输
入序列最接近的字符序列（就是损坏数据最少的那一个）.每个测试数据有唯一的最优解.正确的解
答必须使用到输入文件中的所有数据.
输入格式:
两个输入文件都以一个整数 N 开始（19 < N < 1200）,表示接下去的行数.
N
(位 1)(位 2)(位 3) ... (位 20)
(位 1)(位 2)(位 3) ... (位 20)
...
每行有 20 位的宽度.在 0 和 1 之间没有空格分开.
文件 font.in 描述字体.它总有 541 行.它在每个测试数据中可能不同.
输出格式:
你的程序必须建立一个输出文件,包含一个识别出来的字符串.它的格式是一个单行的 ASCII 文本.
输出文件中不应该包含任何分隔符.如果你的程序没有识别出一个特定的字符,就必须在适当的位
置输出一个“?”.
样例输入:
见提示。
样例输出:
a
提示:
样例输入：
| 例:font.in 的开头（不完全的） , 有“空格”和“a” |
例:char.in 显示了一个损坏的 “a” |
| font.in | char.in |
|
540 00000111111011000000 |
19 00000000000000000000 00000000000000000000 00000000000000000000 00000011100000000000 00100111011011000000 00001111111001100000 00001110001100100000 00001100001100010000 00001100000100010000 00000100000100010000 00000010000000110000 00001111011111110000 00001111111111110000 00001111111111000000 00001000010000000000 00000000000000000000 00000000000001000000 00000000000000000000 00000000000000000000 |
| 图 1a | 图 1b |
注意,上面输出的一行是两个字符:“a”后面还跟着一个空格.（这是按原文译的,其实我也不理解这句话,应该只有一个字符“a”吧——译者注）
时间限制: 1000ms空间限制: 32MB
来源: USACO-第5章