会津タカダ市が生産販売する布製コースターは、対称なデザインでとても美しいことで知られている。会津タカダ市では品質管理の一環として、製造ラインにカメラを設置し、各コースターを撮影して得られた画像が対称になっているかを自動で検証している。各コースターは N × N ピクセルの正方形の白黒画像として表される。各ピクセルは白または黒の画像に対応して、0 または 1 の値をとる。
この度、生産ラインの機器更新にともなって、画像解析システムのソフトウェアを更新することになった。新システムでは、通信データ量を削減する工夫がなされ、以下の方法でカメラから解析システムにデータが送られてくる。
C 枚のコースターについて、1枚目の画像のピクセル情報と続く C - 1 枚分の差分情報を入力し、上下対称かつ左右対称となっているコースターの枚数を報告するプログラムを作成せよ。
入力は以下の形式で与えられる。
C N p11p12...p1N p21p22...p2N : pN1pN2...pNN diff1 diff2 : diffC−1
1行目にコースターの枚数 C (1 ≤ C ≤ 10000) と画像の縦と横のピクセル数 N (2 ≤ N ≤ 1000 かつ N は偶数) が与えられる。2行目から N + 1 行目に最初のコースターの画像のピクセルを表す N行 × N 列の数字 pij (pij は 0 または 1)が与えられる。
N + 2 行目以降に、2枚目以降のコースターの情報を表す差分 diffi が次の形式で与えられる。
D r1 c1 r2 c2 : rD cD
1行目に変化したピクセルの数 D (0 ≤ D ≤ 100) が与えられる。続くD 行に変化したピクセルの行と列の番号をそれぞれ表す ri とci (1 ≤ ri, ci ≤ N) が与えられる。diffi の中に、同じ位置は2回以上与えられない。
上下対称かつ左右対称となっているコースターの枚数を1行に出力する。
7 8 00100000 00011000 10111101 01100110 01000110 10111101 00011000 00100100 2 5 3 1 6 1 6 8 3 6 8 3 3 3 6 2 6 3 6 6 0 2 3 8 6 8
3
入力例1のコースターの画像を以下に示す。この場合、2枚目、5枚目、6枚目のコースターが上下対称かつ左右対称となるため、3と報告する。
1 6 000000 000000 010010 010010 000000 000000
1
2 2 00 00 4 1 1 1 2 2 1 2 2
2