006 - 品質管理

時間制限 2 秒 / メモリ制限 256 MB / 得点 13 / x 4 /


TLE
2sec
MLE
256MB
得点
13

会津タカダ市が生産販売する布製コースターは、対称なデザインでとても美しいことで知られている。会津タカダ市では品質管理の一環として、製造ラインにカメラを設置し、各コースターを撮影して得られた画像が対称になっているかを自動で検証している。各コースターはN×Nピクセルの正方形の白黒画像として表される。各ピクセルは白または黒の画像に対応して、0または1の値をとる。
この度、生産ラインの機器更新にともなって、画像解析システムのソフトウェアを更新することになった。新システムでは、通信データ量を削減する工夫がなされ、以下の方法でカメラから解析システムにデータが送られてくる。

  • ラインに流れてくる最初のコースターの情報は、N×Nピクセルの画像としてシステムに送られてくる。
  • 2枚目以降のコースターの情報は、1つ前に送られた画像との差分だけが送られてくる。差分は、「0から1」または「1から0」へと変化したピクセルの位置の集合として与えられる。

課題

C枚のコースターについて、1枚目の画像のピクセル情報と続くC-1枚分の差分情報を入力し、上下対称かつ左右対称となっているコースターの枚数を報告するプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

C N
p11 p12…p1N
p21 p22…p2N
:
pN1 pN2…pNN

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回以上与えられない。

時間制限

入力に対して、実行時間が5秒を超えてはならない。

出力

上下対称かつ左右対称となっているコースターの枚数を1行に出力する。

入出力例

入力例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

出力例1

3

入力例1のコースターの画像を以下に示す。この場合、2枚目、5枚目、6枚目のコースターが上下対称かつ左右対称となるため、3と報告する。

入力例2

1 6
000000
000000
010010
010010
000000
000000

出力例2

1

入力例3

2 2
00
00
4
1 1
1 2
2 1
2 2

出力例3

2