WAYS2 - FREE PATHS


Problem Statement:

Consider a block of m rows and n columns. At each step you can move

one step to the right or one step to bottom or one step to bottom-right.

i.e.   if you are currently at (x,y)      : x-row, y-column

u can either move to (x,y+1) or (x+1,y) or (x+1,y+1)

 

You’ve to find the number of possibilities to reach the point (A,B) from (0,0).

 

Unluckily you cannot step into some places where bombs are placed denoted by “@”.

 

Input:

 

The first line consists of 2 integers m and n denotes the number of rows and columns.

Then the description of the m x n block is given.

(‘0’- if the path is free to move and ‘@’-if the path has bombs and u cannot move to that place)

Then an integer t follows which denotes the number of test cases.

Then for next t lines each line consists of 2 integers A and B.

 

Output:

For each test case print the number of possibilities of reaching (A,B) from (0,0) in separate lines.

 

Input Constraints:

2<=m<=10

2<=n<=10

m>A>=0

n>B>=0

 

EXAMPLE:

SAMPLE INPUT:

3 6

000@@@

@@00@@

@@000@

8

0 1

0 4

1 3

2 3

2 4

1 2

2 2

2 5

 

SAMPLE OUTPUT:

1

0

3

7

10

2

2

0

 

EXPLANATION OF THE TESTCASE:


 

From the figure clearly u can see that there are 3 paths to (1,3), 7 paths to (2,3), 10 paths to (2,4) and so..


Note: if u can't see the image clearly goto the following link:

https://docs.google.com/uc?id=0B0rk3iRD6D_JYjAxMzAxNTEtYjU3YS00OWVhLWEyNzgtOWUzN2NmMmRmZDJh&export=download&authkey=CK-7vYoI&hl=en_US


 

Added by:cegprakash
Date:2011-05-20
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:own problem

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.