【電脳少女プログラミング2088 ─壊レタ君を再構築─】「一番通りの繁華街」を解いてみた（Ruby）

キャンペーン実施中ということで、問題を解いてみました。
問題：一番通りの繁華街 - スキルチェックB相当

paizaは問題名が面白くて好きです。
早速解いていきます。

問題概要

N×Nの広さの地域があり、ギャングのアジトは'.', 何もない場合は'#'で表される。
アジト同士を線で繋いだ時、正方形になればそこはギャングの縄張りとなる。
Nおよび地域マップが入力されるので、縄張りの数を出力する。

参考例

以下の入力の場合、3つの正方形ができるので3が回答となります。
※小さい縄張りを内包していても一つの縄張りとして換算されます。

5
.#.#.
#####
.#.#.
##.##
.###.

①
. # . # .
#####
. # . # .
## . ##
. ### .

②
. # . # .
#####
. # . # .
## . ##
. ### .

③
. # . # .
#####
. # . # .
## . ##
. ### .

方針

1. 一辺の長さ2 ~ Nの各正方形について、条件を満たすか確認すれば良さそう
2. 5 ≦ N ≦ 50 という制約なので、全探索しても十分間に合いそう

回答

N = gets.to_i
hideouts = []
N.times do
  hideouts << gets.chomp.split('')
end

# 正方形四つの点を返す。範囲外の場合はfalseを返す。
def square_points(grid, h, w, length, n)
  ul = [h, w]
  ur = [h, w + length - 1]
  dl = [h + length - 1 , w]
  dr = [h + length - 1, w + length - 1]

  # 範囲判定
  if (w + length - 1) > (n - 1) || (h + length - 1) > (n - 1)
    return false
  else
    return [ul, ur, dl, dr]
  end
end

square_count = 0 # 回答を保持
for i in 2..N do # 辺の長さそれぞれでループ
  for j in 0...N do # 縦それぞれ
    for k in 0...N do # 横それぞれ
      points = square_points(hideouts, j, k, i, N)
      next if points == false
      ok = true
      # 4点について、一つでもアジト以外であればflagをfalseに変更
      points.each do |p|
        ok = false if hideouts[p[0]][p[1]] == '#'
      end
      square_count += 1 if ok == true
    end
  end
end

puts square_count

回答ざっくり解説

1. とりうる辺の長さ（2 ~ N）全てについてforループを回す（i）
2. 縦列それぞれ（j）・横列それぞれ（k）でループを回し、一点ずつ確認していく
3. square_pointsという、与えられた点・辺の長さから正方形を構成する4点を返すメソッドを定義し、各辺の長さ・点について実行 ※範囲外であればfalseを返す
4. 受け取った4点全てアジト（.）であれば縄張り = 何もない場所(#)がある場合は領域ではないのでフラグをfalseに変更
5. もしflagがtrueのままであれば縄張りの数（square_count）をインクリメントする

みたいな感じです。
範囲外の場合における不要な判定（辺の長さ = Nの場合でも、全ての点について確認しているなど）はありますが、N が50以下なので特に問題になりませんでした。綺麗ではないですが笑
こういうgridの問題はループに入る前、square_pointsのような関数を作成してしまうと分かりやすいかなと感じています。

効率面は微妙かもしれませんが、条件的に上記で問題ありませんでした。
フィードバックでは、

ガガ……ピー……効率……並行処理……ガ……
ともらったので、並行処理についても改善してみたいと思っています。また、再度見直して単純なリファクタリングもするかもです。（やったら追記したいですね。）

お読みいただきありがとうございました！
別問題にもトライしていきますmm