Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
N \times N のグリッドがあり、このグリッドの上から i マス目、左から j マス目を (i,j) と呼びます。
このグリッドの各マスには高々 1 個のコマが置かれています。
グリッドの状態は N 個の文字列 S_i として与えられ、
- S_i の j 文字目が
O
であるとき (i,j) に 1 つコマが置かれていること - S_i の j 文字目が
X
であるとき (i,j) にコマは置かれていないこと
を表します。
整数 M が与えられます。 この M を使って、 (s,t) に置かれているコマ P について、以下の条件を全て満たすマス (u,v) を P が守っているマスと定義します。
- s \le u \le N
- t \le v \le N
- (u - s) + \frac{(v - t)}{2} < M
Q 個のマス (X_i,Y_i) について、そのマスを守っているコマの個数を求めてください。
制約
- N,M,X_i,Y_i,Q は整数
- 1 \le N \le 2000
- 1 \le M \le 2 \times N
- S_i は
O
,X
からなる - 1 \le Q \le 2 \times 10^5
- 1 \le X_i,Y_i \le N
入力
入力は以下の形式で標準入力から与えられる。
N M S_1 S_2 \vdots S_N Q X_1 Y_1 X_2 Y_2 \vdots X_Q Y_Q
出力
Q 行出力せよ。
そのうち i ( 1 \le i \le Q ) 行目には、マス (X_i,Y_i) を守っているコマの個数を整数として出力せよ。
入力例 1
4 2 OXXX XXXX XXXX XXXX 6 1 1 1 4 2 2 2 3 3 1 4 4
出力例 1
1 1 1 0 0 0
マス (1,1) のみにコマが置かれ、このコマによって以下の #
のマスが守られます。
#### ##.. .... ....
入力例 2
5 10 OOOOO OOOOO OOOOO OOOOO OOOOO 5 1 1 2 3 3 4 4 2 5 5
出力例 2
1 6 12 8 25
入力例 3
8 5 OXXOXXOX XOXXOXOX XOOXOOXO OXOOXOXO OXXOXXOX XOXXOXOX XOOXOOXO OXOOXOXO 6 7 2 8 1 4 5 8 8 3 4 1 7
出力例 3
5 3 9 14 5 3
Score : 600 points
Problem Statement
We have an N \times N grid. The square at the i-th row from the top and j-th column from the left in this grid is called (i,j).
Each square of the grid has at most one piece.
The state of the grid is given by N strings S_i:
- if the j-th character of S_i is
O
, then (i,j) has a piece on it; - if the j-th character of S_i is
X
, then (i,j) has no piece on it.
You are given an integer M. Using this M, we define that a piece P placed at (s,t) covers a square (u,v) if all of the following conditions are satisfied:
- s \le u \le N
- t \le v \le N
- (u - s) + \frac{(v - t)}{2} < M
For each of Q squares (X_i,Y_i), find how many pieces cover the square.
Constraints
- N, M, X_i, Y_i, and Q are integers.
- 1 \le N \le 2000
- 1 \le M \le 2 \times N
- S_i consists of
O
andX
. - 1 \le Q \le 2 \times 10^5
- 1 \le X_i,Y_i \le N
Input
Input is given from Standard Input in the following format:
N M S_1 S_2 \vdots S_N Q X_1 Y_1 X_2 Y_2 \vdots X_Q Y_Q
Output
Print Q lines.
The i-th line ( 1 \le i \le Q ) should contain the number of pieces that covers (X_i,Y_i) as an integer.
Sample Input 1
4 2 OXXX XXXX XXXX XXXX 6 1 1 1 4 2 2 2 3 3 1 4 4
Sample Output 1
1 1 1 0 0 0
Only Square (1,1) contains a piece, which covers the following #
squares:
#### ##.. .... ....
Sample Input 2
5 10 OOOOO OOOOO OOOOO OOOOO OOOOO 5 1 1 2 3 3 4 4 2 5 5
Sample Output 2
1 6 12 8 25
Sample Input 3
8 5 OXXOXXOX XOXXOXOX XOOXOOXO OXOOXOXO OXXOXXOX XOXXOXOX XOOXOOXO OXOOXOXO 6 7 2 8 1 4 5 8 8 3 4 1 7
Sample Output 3
5 3 9 14 5 3