問題

提出解答

問題の概要

$1 \leq i \leq H, 1 \leq j \leq W$ に対して文字 $C_{i,j}$ があり, $C_{i,j}$ は ${\tt S}, {\tt .}, {\tt \#}$ のどれかである. また, $C_{i,j}={\tt S}$ であるような $(i,j)$ は唯一つである.

このとき, 以下を満たすような整数の組の列 $( (x_0,y_0), (x_1, y_1), \dots, (x_k,y_k))$ は存在するか?

$k \geq 4$
$C_{x_0, y_0}=C_{x_k, y_k}={\tt S}$
$1 \leq p \leq k$ に対して, $C_{x_p, y_p}={\tt .}$
$1 \leq p \lt q \leq k$ に対して, $(x_p,y_p) \neq (x_q, y_q)$
$p=0,1,2, \dots, k-1$ に対して, $\left \lvert x_{p+1}-x_p \right \rvert+\left \lvert y_{p+1}-y_p \right \rvert=1$

制約

$H,W$ は $2$ 以上の整数で $HW \leq 10^6$
$C_{i,j}$ は ${\tt S}, {\tt .}, {\tt \#}$ のどれか
$C_{i,j}={\tt S}$ となる $(i,j)$ が唯一存在する.

解法

一般的なグラフ理論において, 以下が成り立つ.

定理 1

単純無向グラフ $G=(V,E)$ と頂点 $v \in V$ に対して, 以下は同値である.

(a) $G$ には $v$ を含む長さ $3$ 以上のサイクルが存在する.
(b) $G$ から頂点 $v$ を除いた部分グラフを $H$ とする. $G$ における相異なる2つの $v$ の近傍 $u,w$ のうち, $H$ において $u,w$ が同じ連結成分にあるようなものが存在する.

(a) が成り立つ時, 長さ $3$ 以上のサイクルを $x_1, x_2, \dots, x_k, x_1~(k \geq 3, v=x_1)$ とする. このとき, $x_2, x_k$ は $x_1$ の相異なる $x_1$ の近傍である.

一方で, (b) が成り立つとき, $G$ における相異なる近傍で $H$ 上連結な2頂点を $u,w$ とする. このとき, $uw$ パスを $u=y_1, \dots, y_k=w$ としたとき, $k \geq 2$ である. このとき, $v,u=y_1, y_2, \dots, y_k=w, v$ は $H$ 上のパスであり, 長さは $(k+1)$ で, $3$ 以上である.