📄 epattern.html
字号:
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=gb2312">
<META NAME="GENERATOR" CONTENT="Mozilla/4.03 [zhcn] (Win95; I) [Netscape]">
<TITLE>1996 ACM Finals, Problem E - Pattern Matching Prelims</TITLE>
<!SGML "ISO 8879:1986">
</HEAD>
<BODY BGCOLOR="#FFFFFF">
<HR NOSHADE>
<CENTER>
<H1>
1996 ACM Scholastic Programming Contest Finals</H1></CENTER>
<CENTER>
<H4>
sponsored by Microsoft</H4></CENTER>
<CENTER>
<H1>
Problem E</H1></CENTER>
<CENTER>
<H2>
Pattern Matching Prelims</H2></CENTER>
<CENTER>
<H3>
Input file: pattern.in</H3></CENTER>
Some algorithms for optical character recognition compare a scanned image
with templates of "perfect" characters. Part of the difficulty with such
comparisons is deciding where to start the comparison. This is because
the characters in the scanned image are subject to noise and distortion,
resulting in changes in size, position, and orientation. A procedure that
is sometimes used to deal with changes in position matches the "center
of gravity" of the scanned character and the templates against which it
is compared. In this problem you are to determine the &quotcenters
of gravity" of scanned images of characters.
<P>For our purposes, a scanned image will be a rectangular array of real
numbers, each of which represents the gray-scale value of a point in a
scanned image. Each gray-scale value will be between 0 (representing a
totally white region) and 1 (representing a totally black region). The
array will have no more than 25 rows and 25 columns.
<P>The center of gravity is a particular element of an array. Suppose a
center of gravity is in the ith row and jth column. Then the difference
between the sum of the elements of the two array portions above and below
the ith row is minimal. Likewise, the difference of the sums of the elements
in the two array portions to the left and to the right of the jth column
is minimal.
<P>Consider the array shown below, which might have resulted from scanning
a lower case "to." The center of gravity for this array is uniquely in
row 3, column 3. The difference of the sum of the elements in each array
portion formed by ignoring the third row is 0.1 (the sums are 5.55 and
5.65). The difference of the sum of each array portion formed by ignoring
the third column is 0.0 (the sums are both 5.60).
<CENTER></CENTER>
<CENTER><IMG SRC="pattern.gif" ></CENTER>
<H3>
<HR>Input</H3>
The input will consist of a sequence of scanned character images. Input
for each image will begin with two integers specifying the number of rows
and columns in the scanned data. This will be immediately followed by the
scanned gray-scale data given in row-major order. A pair of zeroes will
follow the data for the last input image.
<H3>
<HR>Output</H3>
For each input character image, display its number (they are sequentially
numbered starting with 1) and the row and column corresponding to the center
of gravity. If there is more than one center of gravity, the one with the
largest row and column should be displayed. The sample that follows illustrates
a reasonable output format.
<H3>
<HR>Sample Input</H3>
<PRE>5 5
0.1 0.2 0.1 0.2 0.1
0.1 0.2 0.3 0.1 0.1
0.2 0.3 0.1 0.1 0.3
0.4 0.1 0.1 0.1 0.2
0.2 0.2 0.3 0.3 0.1
5 10
0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.1
0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2 0.2
0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3 0.3
0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4 0.4
0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.5 0.6
0 0</PRE>
<H3>
<HR>Output for the Sample Input</H3>
<PRE>Case 1: center at (3, 3)
Case 2: center at (4, 6)</PRE>
<HR NOSHADE>
</BODY>
</HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -