一个路径的统计问题,作不出来,请大家看看怎么编程实现

Problem Description
JRY is so rich that he creates an m demensional space and n sight spots inside. Because of special technical problem, all the coordinates are integers between [0,2]. The roads in this space are all parallel to the axis, so the distance between two sight spots is their Manhattan distance. More specifically, if the coordinate of one sight spot is (x1,x2,…,xm), and that of another sight spot is (y1,y2,…,ym), then their distance is ∑mi=1|xi−yi|. JRY wants to establish some bus routes between two sight spots, so he needs to do some research first. For you, the problem is to find the total number of pairs (x,y) for each k, that the distance between (x,y) is k. Please be aware: 1. (x,x) does not count; 2. (x,y) and (y,x) are identical, so that it is only one pair; 3. different sight spots may have same coordinates.

Input
The first line of the input is a single integer T (T=11), indicating the number of testcases.

For each testcase, the first line contains two integers n and m. Each of the following n lines contains one string of length m, which consists three types of characters 0,1,2, and the j-th character of the i-th string means the j-th coordinate of the i-th spot. It is guaranteed that the m of the i-th testcase is i, and for all testcases ∑n≤300000.

Output
For each testcase, print 2m+1 lines. The single number in the i-th line of the output indicates the number of pairs of sight spots with distance i−1

Sample Input
2
2 1
0
1
6 2
00
01
10
11
02
00

Sample Output
0
1
0
1
7
6
1
0

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问