问题 4726 --2009年 珠海赛 Horse in Chinese Chess

4726: 2009年 珠海赛 Horse in Chinese Chess

时间限制: 1 Sec  内存限制: 256 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

As we know, Chinese Chess is an interesting riddle, maybe all of you are good at it, 

and if you are a good programmer at the same time, you can write a program of playing 

Chinese Chess, and then you can play the game with your computer.

Now, we concentrate on the "Horse". 

As we known how the manner horses moves, a horse on the red point can go to the 8 

green points in the figure I unless the green points is blocked or the point is out of 

the board.

The horse is as the same as the knight in the western chess except a manner, which we 

call it 绊马腿” in Chinese.

As the Figure I show, the first step to a direction is the Ban point and the horse 

is forbidden to get there.

Now you are given a chessboard with size of n * m, and there are several blocked 

points on it. And you are given some candidate points to put a horse there.

And then you are asked that how many ways your horses can move to the aim point (x, y) 

after exactly L steps.

输入

The first line contains a number T, indicating the number of cases following.

Each case first contain five integer number n, m, k, p, q ( 4<=n, m<=20; 0<=k, p, q<=20) 

Then following k coordinate points (xi, yi) (1<= i <= k) to put your horse

Then following points (xi, yi) (1<= i<= p) of p block points.

After that, there are q queries below. Each query contain three integers x y L, 

position (x, y) is the aim and you can move exactly L (1<=L<=100) steps. You can assure 

all the points referred are on the board and labeled from 1, and 1 <= x <= n, 1 <= y <= m.

输出

For each query you should output an integer number a line indicating the number of 

ways reaching the position after all of the moving. 

For the result may exceed the range of 32_bit integer, you are allowed to only output 

the result module 2008.

After the output of each case, you should leave a blank line.

样例输入

1<br/>4 4 1 1 1<br/>1 1<br/>3 2<br/>2 3 3

样例输出

2

提示

 

来源

[提交][状态]