当前位置：首页 > news >正文

UVa 250 Pattern Matching Prelims

news 2026/5/22 0:57:20

题目分析

本题属于光学字符识别（OCR\texttt{OCR}OCR）中的预处理问题。在字符识别过程中，扫描得到的图像往往存在噪声、形变，导致字符的大小、位置和方向发生变化。为了能够将扫描图像与标准模板进行匹配，需要找到图像中的一个基准点——重心（Center of Gravity\texttt{Center of Gravity}Center of Gravity），作为对齐的参考点。

重心的定义

对于一个n×mn \times mn×m的灰度矩阵，每个元素的值在[0,1][0,1][0,1]之间，000表示白色，111表示黑色。重心的位置由行和列分别独立确定：

行的选择：假设重心在第iii行，那么忽略第iii行后，上方所有行的元素之和与下方所有行的元素之和的差值应尽可能小。
列的选择：类似地，忽略第jjj列后，左侧所有列的元素之和与右侧所有列的元素之和的差值应尽可能小。

特别地，如果存在多个满足最小差值的行或列，则选择行号最大、列号最大的那一组。

输入输出格式

输入由多组数据组成，每组数据第一行为两个整数RRR和CCC，分别表示矩阵的行数和列数，满足1≤R,C≤251 \leq R, C \leq 251≤R,C≤25。接下来是R×CR \times CR×C个浮点数，按照行主序给出。输入以0 0结束。
输出格式：对于每组数据，输出Case k: center at (r, c)，其中kkk从111开始编号。

样例分析

以题目中的5×55 \times 55×5矩阵为例：

0.7 0.75 0.7 0.75 0.8 0.55 0.3 0.2 0.1 0.7 0.8 0.1 0.0 0.0 0.8 0.7 0.0 0.0 0.0 0.8 0.8 0.9 0.8 0.75 0.9

计算各行元素之和：

第111行：3.73.73.7
第222行：1.851.851.85
第333行：1.71.71.7
第444行：1.51.51.5
第555行：4.154.154.15

总行和：12.912.912.9。

对于行i=3i=3i=3（忽略第333行），上方行和 =3.7+1.85=5.553.7 + 1.85 = 5.553.7+1.85=5.55，下方行和 =1.5+4.15=5.651.5 + 4.15 = 5.651.5+4.15=5.65，差值为0.10.10.1。因此重心在第333行。

类似地，计算各列之和，可得重心在第333列。

解题思路

初步思考

最直接的方法是：对于每一行iii，分别计算上方元素和与下方元素和，然后求差值，找到最小差值对应的行。列也类似。时间复杂度为O(R×C×(R+C))O(R \times C \times (R + C))O(R×C×(R+C))。由于R,C≤25R, C \leq 25R,C≤25，这个复杂度完全可行（约25×25×50=3125025 \times 25 \times 50 = 3125025×25×50=31250次操作）。

但我们可以进一步优化。

前缀和优化

注意到“忽略第iii行”后，上方元素和就是第111行到第i−1i-1i−1行的元素之和，下方元素和就是第i+1i+1i+1行到第RRR行的元素之和。因此，如果我们预先计算出每一行的元素和（即行前缀和），就可以在O(1)O(1)O(1)时间内得到任意分割的上下方元素和。

设：

rowSum[i]rowSum[i]rowSum[i]表示原矩阵第iii行的元素之和（1≤i≤R1 \leq i \leq R1≤i≤R）。
prefixRow[i]=∑k=1irowSum[k]prefixRow[i] = \sum_{k=1}^{i} rowSum[k]prefixRow[i]=∑k=1irowSum[k]表示前iii行的元素和。

那么：

忽略第iii行后，上方元素和 =prefixRow[i−1]prefixRow[i-1]prefixRow[i−1]。
下方元素和 =totalSum−prefixRow[i]totalSum - prefixRow[i]totalSum−prefixRow[i]，其中totalSum=prefixRow[R]totalSum = prefixRow[R]totalSum=prefixRow[R]。

差值 =∣prefixRow[i−1]−(totalSum−prefixRow[i])∣=∣totalSum−prefixRow[i]−prefixRow[i−1]∣\big| prefixRow[i-1] - (totalSum - prefixRow[i]) \big| = \big| totalSum - prefixRow[i] - prefixRow[i-1] \big|prefixRow[i−1]−(totalSum−prefixRow[i])=totalSum−prefixRow[i]−prefixRow[i−1]。

同理，对于列：

colSum[j]colSum[j]colSum[j]表示原矩阵第jjj列的元素之和。
prefixCol[j]=∑k=1jcolSum[k]prefixCol[j] = \sum_{k=1}^{j} colSum[k]prefixCol[j]=∑k=1jcolSum[k]。
忽略第jjj列后，左侧元素和 =prefixCol[j−1]prefixCol[j-1]prefixCol[j−1]，右侧元素和 =totalSum−prefixCol[j]totalSum - prefixCol[j]totalSum−prefixCol[j]。
差值 =∣totalSum−prefixCol[j]−prefixCol[j−1]∣\big| totalSum - prefixCol[j] - prefixCol[j-1] \big|totalSum−prefixCol[j]−prefixCol[j−1]。

处理多个最优解

题目要求：如果有多行能使差值最小，选择行号最大的；列同理。因此我们在遍历行和列时，应该从大到小遍历，并仅在遇到更小的差值时才更新答案，这样最后一个遇到的“相等”差值就不会覆盖之前更大的行号。

边界情况

当R=1R=1R=1时，没有“上方”和“下方”行，此时忽略唯一的一行后，上下方和均为000，差值为000，重心行取111。
当C=1C=1C=1时类似。

在代码实现中，我们从R−2R-2R−2开始下降到111，并将初始的最小行设为R−1R-1R−1（最后一行的上一行），初始差值设为∣totalSum∣\big|totalSum\big|totalSum。这样可以正确处理边界。

浮点数精度

由于输入是浮点数，直接比较相等可能因精度问题出错。因此我们使用一个小的容差值EPSILON = 1E-6，在比较temp<minDifferencetemp < minDifferencetemp<minDifference时，使用temp + EPSILON < minDifference来避免浮点误差。

代码实现

// Pattern Matching Prelims// UVa ID: 250// Verdict: Accepted// Submission Date: 2016-05-23// UVa Run Time: 0.040s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constdoubleEPSILON=1E-6;// 浮点数比较的容差值intmain(){cin.tie(0);// 加速输入输出cout.sync_with_stdio(false);vector<double>sumOfRows,sumOfColumns;// 存储行和列的前缀和introw,column,cases=0;while(cin>>row>>column,row&&column)// 读取矩阵大小，遇到0 0结束{sumOfRows.clear();sumOfColumns.clear();sumOfRows.resize(row);// 调整行前缀和数组大小sumOfColumns.resize(column);// 调整列前缀和数组大小fill(sumOfRows.begin(),sumOfRows.end(),0.0);fill(sumOfColumns.begin(),sumOfColumns.end(),0.0);doublevalue;// 读取矩阵元素，同时累加每一行和每一列的和for(inti=0;i<row;i++)for(intj=0;j<column;j++){cin>>value;sumOfRows[i]+=value;// 累加到对应行sumOfColumns[j]+=value;// 累加到对应列}// 计算行前缀和：sumOfRows[i] 现在表示前 i+1 行的元素和for(inti=1;i<sumOfRows.size();i++)sumOfRows[i]+=sumOfRows[i-1];// 计算列前缀和：sumOfColumns[j] 现在表示前 j+1 列的元素和for(intj=1;j<sumOfColumns.size();j++)sumOfColumns[j]+=sumOfColumns[j-1];doubletotal=sumOfRows[row-1];// 矩阵所有元素的总和// 寻找最优行：从最后一行向前遍历，保证遇到相等差值时保留更大的行号intminRow=row-1;doubleminDifference=fabs(total);// 初始差值：忽略第一行时的情况// i 从 row-2 到 1，对应实际行号从 row-1 到 2（因为需要上下都有行）for(inti=row-2;i>=1;i--){// 忽略第 i+1 行（0-indexed）时的差值doubletemp=fabs(total-sumOfRows[i]-sumOfRows[i-1]);// 如果找到更小的差值，更新答案if(temp+EPSILON<minDifference){minRow=i;minDifference=temp;}}// 寻找最优列：从最后一列向前遍历intminColumn=column-1;minDifference=fabs(total);// 初始差值：忽略第一列时的情况for(intj=column-2;j>=1;j--){doubletemp=fabs(total-sumOfColumns[j]-sumOfColumns[j-1]);if(temp+EPSILON<minDifference){minColumn=j;minDifference=temp;}}// 将 0-indexed 转换为 1-indexed 输出minRow++;minColumn++;cout<<"Case "<<++cases;cout<<": center at ("<<minRow<<", "<<minColumn<<")"<<endl;}return0;}