ABC045 D - すぬけ君の塗り絵 / Snuke's Coloring

問題
提出コード
想定解の方がスマートでした。
自分は、mapを使ってごり押しをしました。

解法

素直に全探索することをまず考えてみると、
9マスのうち、左上のマスを決め打ってから9個のマスを確認する、という動作は、左上のマスの候補が

となるので、もちろん間に合いません。
なので、今回は黒いマスの個数がたかだかであることを利用し、
それぞれの黒いマスを含む全ての正方形の取り方について、重複なく数え上げていく
ということを行います。
正方形がすべて白いマスだった場合は、から、黒いマスが1~9個であったパターンの和を引けば求めることができます。
さて、ある黒いマスを1つとってきたときに、その黒いマスを含むような正方形の選び方は9通りです。正方形の上からiマス、左からjマス目の部分にその黒いマスがあったパターン、を考えると自然と9通りになります。
ということで、全ての黒いマスについて、それぞれの9通りのパターンのときに、黒いマスの個数がどうなっているかを調べればいいです。
あとは、これを重複のないよう、そしてマス目がはみ出ることがないように数えていけば、答えが求まります。