| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 512 MB | 7 | 1 | 1 | 100.000% |
アパレル会社のパスカル社長は在庫の服を保管するために幅 W 奥行き H の倉庫を借りて、その倉庫にできるだけたくさんのクローゼットを設置することにした。 その倉庫は幅 1 奥行き 1 のタイルが W * H 枚敷き詰められており、倉庫の入口のドアがちょうど外周のタイルの一つに隣接するように存在している。 また、倉庫内には何本か柱が立っている(ただし、柱が一本も無い場合もある)。 クローゼットは直方体の形をしており、横幅は 2 で、奥行きが 1 である。 幅が 2 である 2 つの面のうち片一方に扉がついている。 扉があるクローゼットの面に向かって、ちょうど左側半分を扉が占めている。
洋服の運び出しはロボットが行う。そのため、倉庫の入り口から、各クローゼットの扉の正面まで、ロボットが通れる経路が存在する必要がある。 ロボットは幅 1 奥行き 1 の大きさで、タイルから 4 方向に隣接するタイルに移動することができる。ただし、クローゼットか柱と重なっているタイルには乗ることができない。
パスカル社長は几帳面な性格なため、クローゼットは必ずちょうどタイル2枚の上に配置するように指示した。 よって、クローゼットの置き方は以下の 4 通りに定まる。
.... .CC. .X.. .... .... ..X. .CC. .... .... .XC. ..C. .... .... .C.. .CX. ....
このとき、パスカル社長が倉庫に設置できるクローゼットの数の最大値を求めよ。
最初の行はテストケースの個数 T を表す正の整数である。 続けて T 個のテストケースが続く。 各テストケースの最初の行には、それぞれスペースで区切られた 2 つの整数 H, W が与えられる。 H, Wはそれぞれ部屋の奥行きと幅を表す。
続いて長さ W の文字列が H 行続く。
c1,1 c1,2 ... c1,W ... cH,1 cH,2 ... cH,W
i 行目の文字列の j 番目の文字 ci,j は部屋の座標 (i, j) が部屋の入口に隣接しているか及びそこに柱があるかどうかを表す。 もし、部屋の入口に隣接している場合 "D"、 柱があれば、"X"、 部屋の入口に隣接しておらず柱もないならば、"." が入力される。
なお "D" は 1 テストケースにつき必ず 1 回出現する。
各テストケースに対し、次のフォーマットの一行を出力しなさい。
Case #X: Y
という内容を1行出力せよ。ここで X は1から始まるテストケース番号、Y は条件にあうように置くことができるクローゼットの個数の最大値である。
3 1 2 D. 3 2 .D .. .. 5 5 ..... ....X .X..D ..X.. .....
Case #1: 0 Case #2: 2 Case #3: 5
Contest > Google > Google's Coding Competitions > Google Code Jam Japan 2011 > Code Jam Japan 2011 決勝 D1번