← 返回题目列表

AtCoder · joi2018ho_c

C. 团子制造者

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

配点: 100 点

你是一个包饺子的工匠。现在你要把饺子串起来了。

饺子是竖着的 N 行,横 M 它被放置在一个分为几列的正方形中。每个方格里都有一个饺子 包含 1 块。每个饺子的颜色分别为红色(R)、绿色(G)或白色(W)。您可以从左到右或从上到下继续。 3 从方格中取出饺子并按顺序放置。 1 就在书串上 3 你可以进行单独的刺击。

现在你有红、绿、白三种饺子了。 1 我想制作尽可能多的串,每个串都按这个顺序刺穿。棋子串起来的顺序必须与它们从方格中移除的顺序相同。另外,在同一个饺子里 2 不能插入比书还大的串。

你能包多少串饺子?

課題

当给出有关放置在正方形中的团子颜色的信息时,红色、绿色和白色团子 1 编写一个程序,找出按此顺序插入每块可以制作的最大串数。


入力

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

  • 1 行包含一个整数 N 和 M 以空格作为分隔符。 长度由
  • 继续 N 行 i 行目 (1 \leqq i \leqq N)有R, G, W 组成 写入字符串 M 。这个字符串的 j 文字目 (1 \leqq j \leqq M) 来自上面 i 线,从左起 j 代表该列中方格内饺子的颜色。

出力

最大串饺子数输出到标准输出。 1 行。 例如,在


制限

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

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

小課題

小課題 1 [13 点]

满足以下条件。

  • N \leqq 4.
  • M \leqq 4.

小課題 2 [20 点]

满足以下条件。

  • N \leqq 10.
  • M \leqq 10.

小課題 3 [67 点]

没有其他限制。


入力例 1

3 4
RGWR
GRGG
RGWW

出力例 1

3

如下图所示将饺子串起来, 3 你可以制作一本书。

  • 从上面 1 线,从左起 1 从右边一排的团子开始 取出 3 团子,按顺序穿在串上。
  • 从上面 1 线,从左起 4 从该行的团子向下 3 团子,按顺序穿在串上。
  • 从上面 3 线,从左起 1 从右边一排的团子开始 取出 3 团子,按顺序穿在串上。

4 由于不可能制作多于一根的串, 输出3 。


入力例 2

4 4
RGWR
GRRG
WGGW
WWWR

出力例 2

4

如下图所示将饺子串起来, 4 你可以制作一本书。

  • 从上面 1 线,从左起 1 从右边一排的团子开始 取出 3 团子,按顺序穿在串上。
  • 从上面 1 线,从左起 4 从该行的团子向下 3 团子,按顺序穿在串上。
  • 从上面 2 线,从左起 2 从该行的团子向下 3 团子,按顺序穿在串上。
  • 从上面 2 线,从左起 3 从该行的团子向下 3 团子,按顺序穿在串上。

5 由于不可能制作多于一根的串, 输出4 。


入力例 3

5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW

出力例 3

6