← 返回题目列表

AtCoder · joi2014ho1

A. JOI 徽章

中文机器翻译题面 查看原题

配点: 100 点

日本信息奥林匹克委员会决定制作一面新的 JOI 旗帜,以支持前往台湾奥运会的运动员。

JOI 标志是一个垂直的正方形。 M 线,水平 N 排成一排,每个方格都有一个 J,O,I 中的任意字符 1 一一写着。

JOI 旗の例

日本信息奥林匹克委员会已决定将 JOI 标志与 JOI 旗帜分开。 JOI标志是一个垂直的正方形。 2 线,水平 2 排成一排,每个方格都有一个 J,O,I 中的任意字符 1 一一写着。

JOI 紋章の例

JOI标志中包含的JOI标志的数量是JOI标志中包含的JOI标志的数量。 列中区域的 2 行,横 2 。 这是位置与 JOI 标志相匹配的 J,O,I 的数量(不旋转或翻转)。符合条件的垂直 2 行,横 2 即使列中的区域重叠,也会单独计算。

日本信息奥林匹克委员会 我有 1 张空白纸。空白方块是构成 JOI 标志的方块。 大小为 1 ,J,O,I 随你喜欢 1 您可以写入字符。日本信息奥林匹克委员会是以下组织之一 1 我决定通过执行两个操作来创建一个新的 JOI 标志。

  • 不要对旧的 JOI 标志执行任何操作,并将其用作新的 JOI 标志。请勿使用空白纸。
  • 空白纸 1 通过将文本粘贴到旧 JOI 标记的任何方块上,在任何旧 JOI 标记上写入文本。 1 更改位置。将改变后的JOI标志设置为新的JOI标志。

日本信息奥林匹克委员会希望在新的 JOI 旗帜上包含尽可能多的 JOI 标志。您想要找到新 JOI 标志中可以包含的 JOI 标志的最大数量。

課題

给定旧 JOI 标志和 JOI 标志的信息,编写一个程序来计算新 JOI 标志中包含的 JOI 标志的最大数量。


入力

从标准输入读取以下数据。

  • 1 行中, 2 整数 M, N 以空格作为分隔符。这是一个带有垂直正方形的 JOI 旗帜 M 线,水平 N 这表明它们排成一排。
  • 继续 M 行的每一行包含 N 写入一串字符。每个字母都是 J,O,I ,M 从行顶部开始 从 i 行目 (1 \leqq i \leqq M中写入的字符串左侧开始) j 文字目 (1 \leqq j \leqq N) 从旧的 JOI 标志上方 i 线,从左起 j 表示列中方框中写入的字符。
  • 继续 2 行的每一行包含 2 写入一串字符。每个字母都是 J,O,I ,2 从行顶部开始 从 i 行目 (1 \leqq i \leqq 2中写入的字符串左侧开始) j 文字目 (1 \leqq j \leqq 2) 从 JOI 徽章上方 i 线,从左起 j 表示列中方框中写入的字符。

出力

表示新 JOI 标志中包含的 JOI 标志的最大数量的整数被发送到标准输出。 输出为 1 行。


制限

所有输入数据满足以下条件。

  • 2 \leqq M \leqq 1\,000.
  • 2 \leqq N \leqq 1\,000.

小課題

小課題 1 [30 点]

满足以下条件。

  • M \leqq 50.
  • N \leqq 50.

小課題 2 [70 点]

没有其他限制。


入力例 1

3 5
JOIJO
IJOOO
IIJIJ
JO
IJ

出力例 1

3

旧的 JOI 旗帜和 JOI 标志如问题中的示例所示。从上面 2 线,从左起 4 使用白纸在栏中画出正方形。 如果将其更改为 J ,它将如下所示:

JOI 旗の <var>1</var> 箇所を変更した例

进行这些更改后,JOI 标志应如下所示: 3 有一个区域与JOI标志的布局相同。

JOI 紋章と同じ配置の領域

与JOI标志相同布局的区域是 没有超过 4 的新 JOI 标志,因此新 JOI 标志中包含的 JOI 标志的最大数量为 3 。


入力例 2

2 6
JOJOJO
OJOJOJ
OJ
JO

出力例 2

2

请注意,可以在不使用空白纸的情况下获得最大值。


入力例 3

2 2
JI
IJ
JJ
JJ

出力例 3

0

在此输入/输出示例中,JOI 标志将出现在任何可能的新 JOI 标志上。 1 不包括在内。