Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2634
Collecting Stones

Time Limit: 5 Seconds      Memory Limit: 32768 KB

Trudy is playing a phone game called Collecting Stones. In this game, a robert is placed on the upper-left corner of the board, which consists of 8x8 grids. On each grid, there are less than 2000001 stones. The robert can move up, down, right, up-right and down-right, but can not move into a grid that has already been passed before. All the stones on the grids which were passed by the robert are collected and Trudy is want to know if it is possible to collect exactly M number of stones when the robert arrives at the lower-right corner.

Input:

The first line of input contains a single integer T(T<=20), the number of testcases. In the first line of each testcase, there is a number M described above, and follows 8x8 numbers, which represents the number of stones on each grid. Note that M will not greater than the sum of all stones on the board.

Output:

For each testcase, output "Yes" if there exists a path for the robert to collect exactly M number of stones, output "No" otherwise.

Sample Input:
2
374
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
2032
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50 51 52 53 54 55 56
57 58 59 60 61 62 63 64
Sample Output:
Yes
No

Note for the first sample: A possible path is 1, 10 18, 19, 20, 29, 38, 31, 40, 48, 56, 64.



Author: SHEN, Guanghao
Source: ZOJ Monthly, December 2005
Submit    Status