logo AlgoBeat OnlineJudge
登录 注册

#215474. [TOIP 2025] 同色樓梯和雙色樓梯

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

题目描述

在一個 的方格圖中,每一格都有恰一種顏色,我們用大寫英文字母代表每種顏色。

所謂的「樓梯」是指:連續的某些直行的區段,這些區段的底部位置(下方所在的列)必須是一樣的,而高度則是自左而右逐步加一。注意,一個樓梯圖形的高度與寬度必然是相等的。

所謂的「同色樓梯」是指:一個樓梯其中所涵蓋方格的顏色皆相同。

所謂的「雙色樓梯」是指:一個樓梯其中所涵蓋方格的顏色有恰兩種。

按照以下的範例圖形中,藍色、黃色與綠色分別是寬度(高度)為 的「同色樓梯」。請注意,樓梯與樓梯可能重疊,例如藍色 C 樓梯旁還有一個C樓梯。此外,大樓梯中必然有小樓梯,例如下圖中寬度 的 B 樓梯中有 個寬度 的樓梯。寬度 的 A 樓梯中則含有 個寬度 的樓梯以及 個寬度 的樓梯。

:::align{center} :::

以下的範例圖形中,有標註出所有「雙色樓梯」。

:::align{center} :::

你的任務是算出所有寬度(高度)的同色樓梯或雙色樓梯分別有幾個。

输入格式

  • 分別代表區域高度、區域寬度。
  • 代表該區域的顏色。
  • 代表詢問同色樓梯數量。若 代表詢問雙色樓梯數量。

输出格式

  • 為一非負整數,代表寬度(高度)最大的同色樓梯(雙色樓梯)的寬度(高度)。
  • 皆為非負整數,代表寬度(高度)為 的同色樓梯(雙色樓梯)數量。
  • ,第二行輸出一空行。

样例

样例输入 1

6 8
BCCDDAAA
CCCBBBAB
DDDAAAAB
EBBEAAAA
EBBAAAAA
BBBBABCD
1

样例输出 1

4
48 12 4 1

样例输入 2

3 3
BCC
CCC
DDD
1

样例输出 2

2
9 2

样例输入 3

3 3
BCC
CCC
DDD
2

样例输出 3

3
0 2 1

数据范围与提示

測資限制

  • 為大寫英文字母。
  • 皆為整數。

評分說明

本題共有五組子任務,條件限制如下所示。每一組可有一或多筆測試資料,該組所有測試資料皆需答對才會獲得該組分數。

子任務 分數 額外輸入限制
1 5 ,所有 相同。
2 9 ,
3 22
4 33
5 31