🗂

ABC191 C - Digital Graffiti を辺の数で解く [Ruby]

2021/02/07に公開

Ruby

公式解説では多角形の頂点の数を数える方法が紹介されていましたが、この記事では辺の数を数える方法を解説します。

問題へのリンク

問題概要

$H$ 行 $W$ 列のマス目がある。各マスは黒または白に塗られており、マス目の一番外側のマスは白に塗られていることが保証されている。黒に塗られた部分を多角形として見たとき、これが何角形であるかを求めよ。

制約

$3\leq H,W \leq 10$
黒に塗られた部分は一つの自己交叉のない多角形となる

解法

このような多角形が与えられたとき、

辺の数が $12$ であるため、これは $12$ 角形である。

マスとマスの間の罫線に注目してみると、

各罫線上に存在する辺の数は図の通りである。これらを合計したものが多角形の辺の数であるので、罫線ごとに存在する辺の数を求めていければ良い。

では、ある罫線上に存在する、多角形の辺の数を数えていきたい。

この罫線に注目していく。

罫線のある部分の両隣のマスの色が異なれば、その部分は多角形の辺である。

罫線の両隣のマスを端から（図では左から）順に見ていき、両隣のマスが同じ色から異なる色に切り替わったとき、辺の数としてカウントしていく。

この作業をすべての罫線について行えば、多角形全体の辺の数が求められる。

コード

h, w = gets.split.map(&:to_i)
s = h.times.map{gets.chomp.chars}
# 辺の数をカウントする
cnt = 0

# 各列の間の罫線について調べる
(h-1).times do |i|
  # 罫線の両隣の色が同じであるとき true とするフラグ
  flag = true
  w.times do |j|
    # 両隣のマスが同色から異色に変わったとき辺の数をカウントし、フラグを反転させる
    if flag && s[i][j] != s[i+1][j]
      cnt += 1
      flag = !flag
    # 両隣のマスが異色から同色に変わったときフラグを反転させる
    elsif !flag && s[i][j] == s[i+1][j]
      flag = !flag
    end
  end
end

# 各行の間の罫線について調べる
(w-1).times do |j|
  flag = true
  h.times do |i|
    if flag && s[i][j] != s[i][j+1]
      cnt += 1
      flag = !flag
    elsif !flag && s[i][j] == s[i][j+1]
      flag = !flag
    end
  end
end

puts cnt

ABC191 C - Digital Graffiti を辺の数で解く [Ruby]

問題へのリンク

問題概要

制約

解法

コード

コードへのリンク

Discussion