問題

長さ $9$ の ${\tt \#}, {\tt .}$ からなる文字列 $S_1, \dots, S_9$ がある.

座標平面において, $1 \leq i \leq 9, 1 \leq j \leq 9$ に対して, $S_i[j]={\tt \#}$ であるとき, 座標 $(i,j)$ にポーンがあり, そうでないならばなにもない.

座標平面上の正方形のうち, 4つの頂点全てにポーンがあるのは何個か?

正方形を作る際, 1辺とその辺に対してどちら側に正方形を作るかによって, 正方形が一意に定める.

ここで, 正方形をなす4頂点はある実数 $x,y$ と非負実数 $dx,dy~( (dx,dy) \neq (0,0))$ を用いて,

$(x,y), \quad (x+dx, y+dy), \quad (x+dy, y-dx), (x+dx+dy, y+dy-dx)\quad$

と表せる.

この問題において, ポーンが存在するのは $x,y$ 座標が $1$ 以上 $9$ 以下の整数であることから, $1 \leq x,y \leq 9, -9 \leq dx,dy \leq 9$ の範囲において全探索, 以下のことをチェックすれば良い.

この全探索において, 同じ正方形を複数回カウントしてしまう可能性がある. これを防止する方法として, 条件を満たす正方形の4頂点を何かしらの方法で並び替えた (例えば辞書式順) 列の集合を作り, 最終的にその集合の大きさを答えれば良い.

計算量はポーンが存在しうる座標の最大値を $N$ として, $O(N^4)$ である.

Kazun の競プロ記録