AtCoder Beginner Contest 269 D問題 Do use hexagon grid
問題
提出解答
問題の概要
問題文の図 にあるように六角形のグリッドがある.
この六角形のうち, 個のマス
は黒であり, それ以外のマスは全て白色である.
このとき, 黒マスはいくつの連結成分からなるか?
制約
解法
今回の問題ではマス に隣接するマスが問題文中に書かれている. これを利用して黒マスを頂点, 隣接するマス同士を結ぶ辺に対する無向グラフの連結成分数を数え上げれば良い. これには BFS や DFS で可能である.
計算量については愚直に行うと 時間, 近傍の求め方を工夫することにより,
時間に落とすこともできる.
