E - パズルの移動

E - パズルの移動解説

実行時間制限: 5 sec / メモリ制限: 256 MB

天下一王国では、あるパズルが大流行しています。このパズルにおいて、 1 × 1 の正方形のブロックを辺でつなげた多角形をピースと呼び、与えられたピースを H × W の長方形に敷き詰めると完成です。

高橋君は、このパズルを完成させました！

しかし、彼は完成させたパズルを人差し指 1 本でどれだけ破壊できるか試したくなったので、左から x 番目、上から y 番目のブロックだけを人差し指で押さえ、下へ引きずるつもりです。あるピースが下に引きずられるブロックを含むとき、そのピースのブロックは全て下に引きずられます。

また、引きずられるブロックの底辺に接続するブロックも一緒に下へ引きずられます。

彼はこの引きずる動作をしたとき、 1 × 1 の正方形のブロックがいくつ動くことになるか、引きずる前に調べたいです。

あなたに高橋君が人差し指で引きずるブロックの位置の候補を Q 個与えます。それぞれの候補に対し、高橋君の動作に伴って引きずられるであろうブロックの数を出力してください。

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

H W
c_{1,1} c_{1,2} ... c_{1,W}
c_{2,1} c_{2,2} ... c_{2,W}
:
c_{H,1} c_{H,2} ... c_{H,W}
Q
x_1 y_1
x_2 y_2
:
x_Q y_Q

1 行目には、パズルの縦のブロック数を表す整数 H (1 ≦ H ≦ 20000)、横のブロック数を表す整数 W (1 ≦ W ≦ 16) がスペース区切りで与えられる
2 行目から H 行は、パズルの情報が与えられる。そのうち i(1 ≦ i ≦ H) 行目には、 W 文字の文字列が与えられる。このうち j(1 ≦ j ≦ W) 番目の文字 c_{i,j} は、上から i 番目、左からj 番目におけるブロックの種類を表す。縦または横に隣り合うブロックが同じ種類の時、その 2 つのブロックは同じピースであることを表す。なお、 c_{i,j} は、必ず大文字アルファベットである
H + 2 行目には、高橋君が引きずる候補の場所の数を表す整数 Q (1 ≦ Q ≦ 100000) が与えられる
H + 3 行目から Q 行は、高橋君が引きずる候補のブロックの場所を表す情報が 1 行ごとに与えられる。そのうち i(1 ≦ i ≦ Q) 行目には i 番目の候補のブロックの場所を表す 2 つの整数 x_i, y_i (1 ≦ x_i ≦ W, 1 ≦ y_i ≦ H) が、スペース区切りで与えられる

Q=1 の全てのテストケースに正解した場合、部分点として 30 点が与えられる。

高橋君が引っ張る場所ごとに、いくつのブロックを引っ張ることが出来るかを、 1 行ずつ Q 行で出力せよ。出力の末尾には改行をいれること。

5 3
AAB
ABB
CDE
FFH
GHH
2
1 1
2 3

15
7

(x,y) を、左から x 番目、上から y 番目のブロックとします。

(1,1) のブロックは A です。 A を下に引きずると、すべてのブロックが引きずられます。 (2,3) は D です。 D を下に引きずると、D,F,G,H が引きずられます。

2 2
AB
BA
2
1 1
2 1

2
2

同じアルファベットが使われていても、別のピースである可能性があることに注意してください。

5 5
AABAA
ACDEA
AFGHA
AIJKA
AAAAA
1
3 1

Bのブロックを引きずることで、全てのブロックを引きずることが出来ます。