Kazun の競プロ記録

競技プログラミングに関する様々な話題を執筆します.

AtCoder Beginner Contest 300 C問題 Cross

AtCoder ABC ABC300 C問題 300 pts

問題
提出解答
問題の概要
- 制約
解法

問題

提出解答

問題の概要

$H$ 行 $W$ 列のマス目がある. 上から $i$ 行目, 下から $j$ 列目のマス目を $(i,j)$ と書く.

各マスは ${\tt \#}, {\tt .}$ のどれかが書かれており, $(i,j)$ には $C_{i,j}$ が書かれている. また, $1 \leq i \leq H, 1 \leq j \leq W$ の少なくとも一方を満たさない場合は $C_{i,j}={\tt .}$ とする.

ここで, 正の整数 $a,b,n$ が以下の条件を全て満たすとき, $(a,b)$ を中心とするサイズ $n$ のバツ印という.

$C_{a,b}={\tt \#}$
$d=1,2, \dots, n$ に対して, $C_{a-d,b-d}, C_{a-d,b+d}, C_{a+d,b-d}, C_{a+d,b+d}$ は全て ${\tt \#}$ である.
$C_{a-(n+1),b-(n+1)}, C_{a-(n+1),b+(n+1)}, C_{a+(n+1),b-(n+1)}, C_{a+(n+1),b+(n+1)}$ のうち, 少なくとも $1$ つは ${\tt .}$ である.

また, 相異なる $2$ つのバツ印はマス同士は頂点を共有せず, 全ての ${\tt \#}$ はあるバツ印を構成する.

$N:=\min (H,W)$ とする. $n=1,2, \dots, N$ に対して, サイズ $n$ のバツ印は何個あるか?

制約

$1 \leq H,W \leq 100$
$C_{i,j}$ は ${\tt \#}, {\tt .}$ のどちらか.
${\tt \#}$ はあるバツ印を構成し, 異なるバツ印を構成するマス同士は頂点を共有しない.

解法

マス $(a,b)$ があるバツ印の中心であることの必要十分条件は $S_{a,b}, S_{a-1,b-1}, S_{a-1,b+1}, S_{a+1,b-1}, S_{a+1, b+1}$ が全て ${\tt \#}$ であることである.

よって, 各マスについて, 中心かどうかを判定し, 中心だった場合はそのサイズを計算することによって, 全てのバツ印を漏れなく重複無く探索できる.

この方針では計算量 $O(HW)$ 時間になる.