Character Recognition
令狐运珧
题意：摘自NOCOW翻译（http://www.nocow.cn/index.php/Translate:USACO/charrec）
描述
这个问题需要你写一个程序完成字符识别的任务。
每个完整的字符图案有 20 行，20 位。每个位是“0”或“1”。图 1a 对应着输入文件中的符号图案。
文件 font.in 包括了27个字符图案的信息，以这样的顺序记录：
_abcdefghijklmnopqrstuvwxyz
其中 _ 表示空格字符。每个完整字符长 20 行。
输入文件包含一个或多个可能损坏的字符图案。一个字符图案可能以这些方式被损坏。
- 最多有一行可能被复制了（就接在原来那一行的下面）
- 最多有一行可能丢失了
- 有些“0”可能被改成“1”
- 有些“1”可能被改成“0”
不会有任何一个字符图案既多余了一行并且又丢失了一行。在测试数据的任何一个字符图案中，“0”和“1”的被改变率不超过 30%。
被复制的那一行中，原来的行和多余的行可能都损坏了，而且损坏的部分可能并不相同。
写一个程序，使用 font.in 提供的字体，在输入文件提供的图象中识别出一个或多个的字符序列。
使用提供的字体图象来识别字符的时候，要找出最佳的多余行或遗漏行，使找出的所有“0”和“1”的变化数量最小。在所有可能的多余行中，只按损坏数据最少的那一行计算。你必须确定和输入序列最接近的字符序列（就是损坏数据最少的那一个）。每个测试数据有唯一的最优解。
正确的解答必须使用到输入文件中的所有数据。
[编辑]题目名称
charrec
[编辑]（两个输入文件的）输入格式
两个输入文件都以一个整数 N 开始（19 <= N < 1200），表示接下去的行数。
N (位1)(位2)(位3) ... (位20) (位1)(位2)(位3) ... (位20) ...
每行有20位的宽度。在0和1之间没有空格分开。
文件 font.in 描述字体。它共有 541 行。它在每个测试数据中可能不同。
[编辑]样例输入
| 不完整的样例font.in的开头（空格和a） | 样例charrec.in，显示了一个损坏的a |
| font.in | charrec.in |
540 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000011100000000000 00000111111011000000 00001111111001100000 00001110001100100000 00001100001100010000 00001100000100010000 00000100000100010000 00000010000000110000 00000001000001110000 00001111111111110000 00001111111111110000 00001111111111000000 00001000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 00000000000000000000 | 19 00000000000000000000 00000000000000000000 00000000000000000000 00000011100000000000 00100111011011000000 00001111111001100000 00001110001100100000 00001100001100010000 00001100000100010000 00000100000100010000 00000010000000110000 00001111011111110000 00001111111111110000 00001111111111000000 00001000010000000000 00000000000000000000 00000000000001000000 00000000000000000000 00000000000000000000 |
| 图1a | 图1b |
[编辑]输出格式
你的程序必须建立一个输出文件，包含一个识别出来的字符串。它的格式是一个单行的 ASCII 文本。输出文件中不应该包含任何分隔符。 如果你的程序没有识别出一个特定的字符，就必须在适当的位置输出一个“?”。
[编辑]样例输出
a
解题思路：
- 参考NOCOW“问题分析”
代码：
/*
ID: zc.rene1
LANG: C
PROG: charrec
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_N 1200
int N;
int standard[27][20][20];
int in[MAX_N][20];
int diff[27][20][MAX_N];
int cost[MAX_N][22];
int choice[MAX_N][22];
int mincost[MAX_N + 1];
void GetFont(FILE *font)
{
int i, j, k;
char s[21];
fscanf(font, "%d\n", &i);
for (i=0; i<27; i++)
{
for (j=0; j<20; j++)
{
fscanf(font, "%s\n", s);
for (k=0; k<20; k++)
{
standard[i][j][k] = s[k] - '0';
}
}
}
}
void GetInput(FILE *fin)
{
int i, j;
char s[21];
fscanf(fin, "%d\n", &N);
for (i=0; i<N; i++)
{
fscanf(fin, "%s\n", s);
for (j=0; j<20; j++)
{
in[i][j] = s[j] - '0';
}
}
}
int GetDiffCount(int i, int j, int k)
{
int m, count = 0;
for (m=0; m<20; m++)
{
if (standard[i][j][m] != in[k][m])
{
count++;
}
}
return count;
}
void GenerateDiff(void)
{
//int diff[27][20][MAX_N];
int i, j, k;
for (k=0; k<N; k++)
{
for (i=0; i<27; i++)
{
for (j=0; j<20; j++)
{
diff[i][j][k] = GetDiffCount(i, j, k);
}
}
}
}
void GenerateCost(void)
{
//int cost[MAX_N][3];
int i, j, k, m, n, max = 500;
int head[21], tail[21];
for (i=0; i<N; i++)
{
cost[i][19] = max;
cost[i][20] = max;
cost[i][21] = max;
}
memset(choice, -1, MAX_N * 22 * sizeof(int));
for (i=0; i+18<=N-1; i++)
{
//cost[i][19]
for (j=0; j<27; j++)
{
head[0] = 0;
for (k=1; k<=19; k++)
{
head[k] = head[k - 1] + diff[j][k - 1][i + k - 1];
}
tail[0] = 0;
for (k=1; k<=19; k++)
{
tail[k] = tail[k - 1] + diff[j][20 - k][i + 19 - k];
}
for (k=0; k<=19; k++)
{
if (head[k] + tail[19 - k] < cost[i][19])
{
cost[i][19] = head[k] + tail[19 - k];
choice[i][19] = j;
}
}
}
//cost[i][20]
if (i + 19 <= N - 1)
{
for (j=0; j<27; j++)
{
n = 0;
for (m=0; m<20; m++)
{
n += diff[j][m][i + m];
}
if (n < cost[i][20])
{
cost[i][20] = n;
choice[i][20] = j;
}
}
}
//cost[i][21]
if (i + 20 <= N - 1)
{
for (j=0; j<27; j++)
{
head[0] = 0;
for (k=1; k<=20; k++)
{
head[k] = head[k - 1] + diff[j][k - 1][i + k - 1];
}
tail[0] = 0;
for (k=1; k<=20; k++)
{
tail[k] = tail[k - 1] + diff[j][20 - k][i + 21 - k];
}
for (k=0; k<=20; k++)
{
if (head[k] + tail[20 - k] < cost[i][21])
{
cost[i][21] = head[k] + tail[20 - k];
choice[i][21] = j;
}
}
}
}
}
}
void GenerateMinCost(FILE *fout)
{
//mincost[i] = min(cost[i][19] + mincost[i+19], cost[i][20] + mincost[i+20], cost[i][21] + mincost[i+21])
int i, next, max = 99999999;
int ch[MAX_N + 1];
for (i=0; i<=N; i++)
{
mincost[i] = max;
}
mincost[N] = 0;
for (i=N-19; i>=0; i--)
{
if (i + 19 <= N && mincost[i + 19] < max && cost[i][19] + mincost[i + 19] < mincost[i])
{
mincost[i] = cost[i][19] + mincost[i + 19];
ch[i] = 19;
}
if (i + 20 <= N && mincost[i + 20] < max && cost[i][20] + mincost[i + 20] < mincost[i])
{
mincost[i] = cost[i][20] + mincost[i + 20];
ch[i] = 20;
}
if (i + 21 <= N && mincost[i + 21] < max && cost[i][21] + mincost[i + 21] < mincost[i])
{
mincost[i] = cost[i][21] + mincost[i + 21];
ch[i] = 21;
}
}
next = 0;
while (next < N)
{
if (choice[next][ch[next]] > 0)
{
fprintf(fout, "%c", choice[next][ch[next]] + 'a' - 1);
}
else
{
fprintf(fout, " ");
}
next += ch[next];
}
fprintf(fout, "\n");
}
int main(void)
{
FILE *font, *fin, *fout;
font = fopen("font.in", "r");
fin = fopen("charrec.in", "r");
fout = fopen("charrec.out", "w");
GetFont(font);
GetInput(fin);
GenerateDiff();
GenerateCost();
GenerateMinCost(fout);
return 0;
}
类似资料：