No.866 レベルKの正方形

レベル : / 実行時間制限 : 1ケース 6.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 35
作問者 : e869120e869120 / テスター : tatyamtatyam
4 ProblemId : 3318 / 出題時の順位表

問題文

注意:この問題は高速な言語でなければ実行時間制限に間に合わない可能性があります。

$H$ * $W$ のマス目があります。上から $i$ 行目、左から $j$ 列目のマスを $(i, j)$ と表します。左上のマスは $(1, 1)$、右下のマスは $(H, W)$ となります。
さて、マス $(i, j)$ には英小文字 $c_{i, j}$ が書かれています。

左上のマスが $(a, b)$, 右下のマスが $(c, d)$ $(1 \leq a \leq c \leq H, 1 \leq b \leq d \leq W, c-a=d-b)$ である正方形領域について、この正方形領域の中に含まれる文字の種類数がちょうど $P$ 種類の時、この正方形を「レベル $P$ の正方形」とします。
レベル $K$ の正方形がいくつ存在するか求めて下さい。

制約

全ての入力データは以下の制約を満たします。

  • $H, W$ は $1$ 以上 $2 \ 000$ 以下の整数
  • $K$ は $1$ 以上 $26$ 以下の整数
  • $c_{i, j}$ は a から z までの英小文字のうちいずれかである

入力

$H$ $W$ $K$
$c_{1, 1}c_{1, 2}c_{1, 3}$...$c_{1, W}$
$c_{2, 1}c_{2, 2}c_{2, 3}$...$c_{2, W}$
$c_{3, 1}c_{3, 2}c_{3, 3}$...$c_{3, W}$
...
$c_{H, 1}c_{H, 2}c_{H, 3}$...$c_{H, W}$

出力

最後に改行してください。

サンプル

サンプル1
入力
4 4 6
abcd
bcde
cdef
defg
出力
0

条件を満たす正方形領域はありません。

サンプル2
入力
4 4 3
abcd
bcde
cdef
defg
出力
9

以下の $9$ 個の正方形領域が条件を満たします。

  • 左上 $(1, 1)$, 右下 $(2, 2)$ の正方形領域
  • 左上 $(1, 2)$, 右下 $(2, 3)$ の正方形領域
  • 左上 $(1, 3)$, 右下 $(2, 4)$ の正方形領域
  • 左上 $(2, 1)$, 右下 $(3, 2)$ の正方形領域
  • 左上 $(2, 2)$, 右下 $(3, 3)$ の正方形領域
  • 左上 $(2, 3)$, 右下 $(3, 4)$ の正方形領域
  • 左上 $(3, 1)$, 右下 $(4, 2)$ の正方形領域
  • 左上 $(3, 2)$, 右下 $(4, 3)$ の正方形領域
  • 左上 $(3, 3)$, 右下 $(4, 4)$ の正方形領域
サンプル3
入力
20 20 13
ncununuineuinouicnur
nhuimjiehuiomiojioje
jimiomuimmdrwumuioer
mimiajifhpmiowjiojor
kiojioansngimumapois
jimuipammhupheohmudp
hunpumimhuewijfuhrur
jipamuyfiuhrmpvyxphu
jiamsmxoyuuwhdehuutr
ioamuusuieumhufupyrr
mopmuaiomdumruuruype
popuauximueimurmfumr
ouiweuyoduwiumfryisj
koklnxuamurhphuremeu
immuwmupmpunyaygyweh
mumhxeyomxbwuhamhisd
moumzuihmyoetyrouish
zamuepiioouuomeymgoa
mamouzhoiedieoygmoer
upahumgeyurogebyjajd
出力
119
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。