logo AlgoBeat OnlineJudge
登录 注册

#215872. [JOI 2014 Final] JOI 紋章

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

情報オリンピック日本委員会では,台湾大会に向かう選手を応援するために新しい JOI 旗を作成することにした.

JOI 旗は,正方形が縦に 行,横に 列並んだ形をしており,各正方形には J, O, I のいずれかの文字が 1 つずつ書かれている.

:::align{center}

JOI 旗の例 :::

情報オリンピック日本委員会は JOI 旗とは別に JOI 紋章 というものを決めている.JOI 紋章 は,正方形が縦に 行,横に 列並んだ形をしており,各正方形には J, O, I のいずれかの文字が 1 つずつ書かれている.

:::align{center}

JOI 紋章の例 :::

JOI 旗に含まれる JOI 紋章 の個数とは,JOI 旗に含まれる縦 行,横 列の領域のうち,その領域の J, O, I の配置が JOI 紋章 と(回転や裏返しをせずに)一致しているものの個数のことである.条件を満たす縦 行,横 列の領域同士が重なっていてもそれらを別々に数えるものとする.

情報オリンピック日本委員会は古い JOI 旗と 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 個の整数 が空白を区切りとして書かれている.これは JOI 旗が正方形が縦に 行,横に 列並んだ形であることを表している.
  • 続く 行の各行には,それぞれ 文字からなる文字列が書かれている.各文字は J, O, I のいずれかであり, 行のうち上から 行目 () に書かれている文字列の左から 文字目 () は古い JOI 旗の上から 行目,左から 列目の正方形に書かれている文字を表す.
  • 続く 2 行の各行には,それぞれ 2 文字からなる文字列が書かれている.各文字は J, O, I のいずれかであり,2 行のうち上から 行目 () に書かれている文字列の左から 文字目 () は JOI 紋章 の上から 行目,左から 列目の正方形に書かれている文字を表す.

输出格式

標準出力に,新しい JOI 旗に含まれる JOI 紋章 の個数の最大値を表す整数を 1 行で出力せよ.

样例

样例输入 1

3 5
JOIJO
IJOOO
IIJIJ
JO
IJ

样例输出 1

3

样例输入 2

2 6
JOJOJO
OJOJOJ
OJ
JO

样例输出 2

2

样例输入 3

2 2
JI
IJ
JJ
JJ

样例输出 3

0

数据范围与提示

入出力例 1

古い JOI 旗と JOI 紋章 は問題文中の例の通りである.上から 行目,左から 列目の正方形を白紙を用いて J に変更すると,次のような形になる.

:::align{center}

JOI 旗の 1 箇所を変更した例 :::

このように変更した後の JOI 旗 には次に示す 箇所に JOI 紋章 と同じ配置の領域がある.

:::align{center}

JOI 紋章と同じ配置の領域 :::

JOI 紋章 と同じ配置の領域が 箇所以上となる新しい JOI 旗は存在しないので,新しい JOI 旗に含まれる JOI 紋章 の個数の最大値は である.

入出力例 2

白紙を使用しなくても最大値が得られる場合があることに注意せよ.

入出力例 3

この入出力例の場合,考えられるどの新しい JOI 旗 においても,JOI 紋章 が 1 つも含まれない.

制限

すべての入力データは以下の条件を満たす.

小課題

小課題 1 [30 点]

以下の条件を満たす.

小課題 2 [70 点]

追加の制限はない.