编程介的小学生
2018-12-22 22:58
采纳率: 92.5%
浏览 421

一个机器人移动的距离的计算,是用什么算法实现的?要求C语言,谢谢

Problem Description
QXJ has N robots on the plane, the i-th is at (xi,yi), numbereded 1 to N. Every robot is painted by one kind of color, numbered 1 to M.

Each robots can move K times. In one move,a robot at (x,y) can move to (x−1,y),(x,y+1),(x+1,y),(x,y−1).

After exactly K moves, she wants robots with same color to gather at the same postion and the robot on the i-th color gather at different postion with robots on (i-1)-th or (i+1)-th color.

Now she wants to know how many ways of moving these robots following to rules above.

Two ways are different if one of final postions of certain robot is different or there is at least one robot whose moving path is different.

Input
The first line is the number of test cases T(T≤10).

The first line of each case contains three integer N(1≤N≤200),M(1≤M≤20),K(1≤K≤500), indicating the number of robots ,the number of color and the number of steps robots can move.

The second line,contains M integer mi, indicating the number of robots with the i-th color.

The robots numbered [1,m1] are on the 1st color.The robots numbered [m1+1,m1+m2] are one the 2nd color, ans so on.

The next N line,each contains two integers xi,yi, indicating the postion of i-th robots..

(0≤|xi,yi|≤250).

Output
For each test case, output a single line "Case #x: y", where x is the case number, starting from 1. And y is the answer(module 109+7).

Sample Input
2
3 3 1
1 1 1
1 0
0 1
1 2
4 2 2
2 2
0 1
0 3
0 2
0 4

Sample Output
Case #1: 49
Case #2: 256

  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 收藏
  • 邀请回答

1条回答 默认 最新

  • threenewbee 2019-08-25 22:28
    已采纳
    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题