ABC 401-500/ABC455B - Spiral Galaxy - 競技プログラミング用 知識集積所

---

問題

ABC455B

必要知識

A問題レベルのものは省略

• 全探索※
• 二重ループ※（というか六重ループ）

考え方

問題文の言い回しが難しいが、要は「この領域から切り取った長方形のうち、塗り方が点対称なものはいくつあるか？」ということである。

B問題で「～～のうち、」と来たらまず全探索※を考える。
長方形の位置は、「上の端がどこか」「下の端がどこか」「左の端がどこか」「右の端がどこか」で考えるとよい。
下の端が上の端より上に来ないように注意して上下を二重ループ※で、左右も同様にやると、候補の列挙に四重ループを書くことになる。

その中で、それぞれの長方形の色塗りをチェックする。
これは、上端<=i<=下端かつ左端<=j<=右端である範囲すべてについて

s.at(i).at(j)==s.at(u+d-i).at(l+r-j)

であることを確認すればよい。
これはbool型の「全部trueなら実行したい」をやればよい。
すなわち、trueで初期化したbool型変数を用意して、

s.at(i).at(j)!=s.at(u+d-i).at(l+r-j)

が1つでもあったらfalseに書き換えてやればよい。
これをiとjの二重ループ※で回すので、全体として六重ループになる。

解答例

解答例

注意点

別解