| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 512 MB | 312 | 275 | 220 | 89.431% |
世界的なプログラミングコンテストが日本で開催されることになり,現在会場の設営が行われている.この会場は南北方向に N マス,東西方向に M マスのマス目状に区切られており,いくつかのマスには競技用の機材が置かれている.
このコンテストでは,選手が競技中に休憩するために,軽食や飲み物などを置いた休憩スペースを 1 箇所会場内に設けることになった.休憩スペースは南北方向または東西方向に連続した D マスでなければならない.ただし,機材の置かれたマス目に休憩スペースを設けることはできない.
会場内に休憩スペースを設ける方法は何通りあるかを求めるプログラムを作成せよ.
入力は 1 + N 行からなる.
1 行目には 3 個の整数 N, M, D (1 ≦ N ≦ 100, 1 ≦ M ≦ 100, 2 ≦ D ≦ 100) が空白を区切りとして書かれており,会場が南北方向に N マス,東西方向に M マスのマス目状に区切られており,休憩スペースが南北方向または東西方向に連続した D マスからなることを表す.
続く N 行にはそれぞれ M 文字からなる文字列が書かれており,会場の情報を表す. N 行のうちの i 行目の j 文字目 (1 ≦ i ≦ N, 1 ≦ j ≦ M) は,会場のマス目の北から i 行目,西から j 列目のマスの状態を表す '#' または '.' のいずれかの文字である.'#' はそのマスに機材が置かれていることを,'.' はそのマスに機材が置かれていないことを表す.
会場内に休憩スペースを設ける方法は何通りあるかを 1 行で出力せよ.
3 5 2 ...#. #...# ....#
12
4 7 5 .#..... .....## ....... #......
7
入出力例 1 では,下の図に示すように,休憩スペースを設ける方法は全部で 12 通りある.
※(注記)各入出力例のデータは,右クリック等によりファイルに保存して利用可能です.