Untitled
unknown
plain_text
2 years ago
17 kB
4
Indexable
Write a program to read in and solve path-finding puzzles. Each puzzle consists of an NxN array of integers, like this:
7 4 4 6 6 3 2 2 6 8
3 3 6 5 4 3 7 2 8 3
4 1 6 6 2 4 4 4 7 4
4 5 3 4 3 5 4 4 8 5
5 1 4 6 6 5 0 7 1 4
2 6 9 4 9 7 7 9 1 4
3 5 4 0 6 4 5 5 5 6
6 6 2 3 4 7 1 2 3 3
3 5 4 3 6 5 4 5 2 6
3 9 3 5 1 1 5 4 6 6
The problem is as follows: Starting in the upper left-hand corner (location [0][0]), find a sequence of moves that takes you to the bottom right-hand corner (for an NxN array, this would be location [N-1][N-1]). From each location in the array you may move left, right, up, or down; the number in the location tells you exactly how far to move.
For example, location [0][0] contains a 7, so from there you must move exactly 7 squares, either to the right or down. You cannot move up or left, because that would take you outside the array.
To help you see the solution, the squares along the solution path have been colored orange. From 7 you move right to 2, down to 4, down to 5, up to 5, etc. The complete solution is
[(0, 0), (0, 7), (2, 7), (6, 7), (1, 7), (1, 5), (1, 2),
(7, 2), (7, 4), (7, 8), (4, 8), (5, 8), (5, 9), (9, 9)].
(Also, in the example, there are several squares from which you cannot move at all! Can you find them?)
Input
The first line contains t, the number of test cases followed by a blank space. Each of the t tests start with a number n (n <= 20). Then n + 1 lines follow. In the ith line a number A[i - 1] is given. The (n + 1)th line is a blank space.
Output
If you can reach the destination, print 'YES', otherwise print 'NO'.
Sample
Input
2
8 1 8 6 1 2 5 3 7 9
6 0 3 1 3 8 7 0 4 6
7 4 6 2 2 4 3 9 8 3
7 1 4 0 4 2 3 1 6 6
1 9 4 6 2 4 2 2 3 4
9 5 4 2 5 0 4 8 3 3
3 0 4 3 7 7 5 4 4 4
5 6 8 9 3 7 1 2 9 0
4 0 3 1 0 5 0 5 6 6
9 7 6 5 5 5 3 9 2 2
10
6 4 4 4 1 8 1 5 2 9
0 5 7 2 8 8 0 3 3 5
9 7 8 0 7 2 3 9 5 6
6 6 2 4 6 4 1 3 2 1
4 4 2 0 5 9 7 7 3 3
9 2 7 2 9 1 7 6 0 9
6 3 5 0 8 2 4 2 0 7
5 3 1 5 4 9 3 0 6 7
0 4 2 6 9 8 1 3 6 3
3 2 3 0 0 3 8 1 8 5
Output
YES
YES
21
10
8 1 8 6 1 2 5 3 7 9
6 0 3 1 3 8 7 0 4 6
7 4 6 2 2 4 3 9 8 3
7 1 4 0 4 2 3 1 6 6
1 9 4 6 2 4 2 2 3 4
9 5 4 2 5 0 4 8 3 3
3 0 4 3 7 7 5 4 4 4
5 6 8 9 3 7 1 2 9 0
4 0 3 1 0 5 0 5 6 6
9 7 6 5 5 5 3 9 2 2
10
6 4 4 4 1 8 1 5 2 9
0 5 7 2 8 8 0 3 3 5
9 7 8 0 7 2 3 9 5 6
6 6 2 4 6 4 1 3 2 1
4 4 2 0 5 9 7 7 3 3
9 2 7 2 9 1 7 6 0 9
6 3 5 0 8 2 4 2 0 7
5 3 1 5 4 9 3 0 6 7
0 4 2 6 9 8 1 3 6 3
3 2 3 0 0 3 8 1 8 5
10
3 5 2 3 3 3 4 8 9 2
8 6 7 6 4 4 8 0 4 2
3 5 9 8 4 0 3 3 2 9
1 9 2 9 7 9 7 2 2 8
5 1 2 0 5 0 2 8 2 6
0 9 0 4 8 6 3 9 6 0
8 2 5 3 9 4 1 7 4 1
3 9 7 1 1 6 2 4 2 3
1 6 7 0 8 0 6 9 3 4
9 7 1 7 4 8 3 2 4 4
10
7 4 4 5 0 6 0 5 0 6
5 9 7 6 1 1 8 9 4 3
5 7 0 4 9 2 0 0 1 3
4 8 5 6 0 8 9 0 8 0
8 6 9 4 7 6 1 7 8 8
0 9 2 0 3 6 5 3 8 3
5 7 9 7 8 8 2 2 4 9
9 9 5 5 3 5 7 0 4 3
6 3 4 3 6 1 6 6 0 3
5 4 7 8 4 4 6 9 5 9
10
6 7 7 7 8 2 8 5 4 8
1 7 3 5 2 7 8 7 8 5
9 4 0 7 2 5 0 8 1 2
0 0 9 6 6 2 1 7 8 2
3 5 2 7 3 6 1 0 0 0
6 0 8 0 9 3 5 5 0 8
9 8 8 6 7 0 3 6 1 8
4 6 5 5 9 3 6 1 2 2
3 6 1 3 0 4 7 1 0 5
4 8 1 6 1 5 6 2 2 6
10
2 9 1 2 2 6 7 5 2 2
7 1 3 1 7 7 5 2 2 3
9 4 6 0 2 0 4 0 5 9
2 6 4 9 4 3 6 4 9 3
1 8 5 4 3 5 1 7 3 8
3 9 8 7 2 7 3 4 6 0
5 3 6 2 4 0 8 0 2 8
4 5 2 8 6 1 4 6 9 0
7 8 0 5 1 7 4 3 8 6
4 9 3 5 3 0 2 8 0 9
10
1 2 5 5 0 8 5 4 5 6
7 6 7 1 1 5 1 2 7 6
8 4 9 5 1 6 3 8 5 5
7 5 8 4 3 4 7 1 0 0
2 6 6 2 7 1 2 1 4 9
6 0 7 4 1 6 8 5 9 5
9 8 1 5 1 9 9 6 2 9
3 4 0 9 2 9 6 0 6 3
5 7 9 5 0 3 2 7 5 5
8 9 4 8 0 9 1 4 3 3
10
3 9 8 6 7 5 6 9 0 9
9 8 3 5 2 4 6 8 9 0
5 9 0 5 0 2 5 0 3 1
6 4 0 3 3 8 8 8 7 6
4 4 0 9 5 2 6 6 6 5
4 2 2 3 2 0 4 9 4 3
7 4 2 3 4 0 8 0 6 8
3 6 1 4 7 1 8 8 7 1
5 3 9 2 3 7 5 0 4 9
0 1 1 0 1 5 6 5 7 6
10
1 6 2 9 4 0 8 2 2 1
8 4 9 7 5 7 3 9 1 4
9 8 0 7 5 7 3 5 3 8
9 7 4 0 5 1 3 1 1 6
2 3 5 1 4 4 3 6 8 5
2 4 9 1 2 6 8 5 3 1
1 4 3 2 0 1 9 1 4 3
9 8 7 1 7 7 2 5 2 6
9 8 7 4 1 3 2 6 6 8
9 8 3 7 7 4 0 0 1 6
10
4 7 4 7 9 0 8 9 5 1
7 3 3 8 7 8 2 0 1 1
9 4 3 1 2 9 0 9 7 7
1 9 6 5 7 5 4 3 2 2
4 5 6 0 7 5 8 2 5 7
4 1 8 1 4 3 1 6 2 8
5 3 7 5 2 3 8 2 7 8
5 0 2 0 7 6 3 7 8 5
4 8 2 6 0 4 3 5 1 4
3 1 2 3 3 6 6 6 1 5
10
3 5 0 0 7 7 3 1 7 6
0 2 2 6 1 9 9 5 3 0
0 4 3 4 3 6 9 7 3 5
3 0 7 7 9 1 4 6 7 8
4 0 1 4 7 6 6 7 1 0
1 6 1 0 6 6 2 4 9 1
5 3 9 3 7 7 5 4 6 0
1 2 6 0 4 1 2 7 6 6
0 8 8 4 2 0 9 9 0 7
9 5 1 3 4 8 5 3 5 4
20
7 9 1 17 6 8 18 19 12 18 5 19 15 6 9 3 13 9 14 11
18 19 10 18 11 12 3 5 14 4 14 11 17 6 6 8 6 17 7 18
19 16 11 13 11 4 14 17 6 1 14 4 15 3 14 11 17 1 6 18
8 17 5 13 14 11 9 15 0 6 1 15 5 9 6 2 12 13 19 9
4 8 3 7 19 5 4 19 0 19 1 7 10 11 13 8 14 1 19 12
16 3 5 13 10 13 9 17 13 15 0 15 9 0 7 14 6 17 4 17
10 1 3 4 12 1 6 3 17 1 14 13 19 13 3 16 8 14 6 4
8 0 11 3 12 0 1 0 9 1 15 12 3 0 8 9 11 10 12 3
17 15 3 6 18 0 2 2 12 9 10 10 11 11 7 1 5 5 2 6
14 12 15 13 15 6 10 2 12 2 10 3 6 17 2 1 18 8 14 0
13 5 17 11 5 11 14 17 17 12 17 19 12 0 1 10 6 6 7 11
8 1 8 9 2 12 18 8 3 7 8 19 12 1 17 18 10 1 13 4
11 17 7 3 14 8 17 19 14 17 6 2 7 7 9 9 3 17 9 16
4 12 15 16 13 18 13 19 6 15 6 14 5 1 1 1 7 16 13 10
11 2 8 13 9 14 5 18 17 8 18 13 8 3 6 14 7 9 10 16
0 2 9 3 8 14 8 19 13 4 3 17 2 2 1 13 1 16 3 4
8 6 18 5 3 6 19 11 7 1 14 10 16 14 19 18 17 12 12 14
8 8 16 4 6 14 18 7 6 6 8 1 2 2 18 15 3 8 17 17
18 1 9 6 6 19 2 6 9 17 6 15 5 5 7 11 7 4 12 9
12 6 6 15 3 5 8 12 9 6 7 12 9 5 18 4 14 8 14 2
20
4 15 4 3 18 4 15 12 8 14 15 11 1 7 9 15 8 6 14 11
5 16 16 8 15 19 1 18 4 0 16 11 13 0 9 16 10 10 3 6
15 7 19 3 4 13 8 14 18 4 11 6 1 17 15 13 2 6 13 9
11 16 19 13 11 14 10 8 10 8 6 1 7 8 2 5 5 10 12 17
3 19 14 2 9 17 5 15 17 9 0 5 2 6 11 7 2 14 7 19
1 3 0 9 17 6 13 18 13 10 6 6 9 11 10 16 4 3 16 16
8 19 19 13 12 5 17 12 11 3 16 5 6 17 9 17 5 13 19 8
2 14 3 7 13 16 9 1 9 0 15 6 3 11 6 4 10 3 19 13
6 7 2 2 14 7 2 6 6 18 1 11 12 13 4 15 0 17 7 6
4 5 6 11 2 10 9 11 9 17 14 9 18 15 3 1 2 0 15 8
8 1 5 9 3 19 2 15 10 12 5 12 19 3 0 6 5 18 7 6
8 10 15 17 6 6 16 10 3 8 16 4 4 3 1 4 9 13 8 15
9 3 7 1 18 8 18 13 15 15 12 9 1 18 12 0 6 19 5 3
3 8 1 19 8 3 7 0 19 12 13 18 13 5 0 16 5 9 13 1
14 14 19 5 2 7 18 16 14 3 0 2 11 4 1 14 2 4 18 19
2 9 11 19 18 18 4 12 5 18 12 8 8 2 11 2 4 11 9 10
11 12 12 13 9 3 8 2 3 3 18 13 13 17 19 12 7 12 6 18
3 15 17 13 1 13 17 18 18 1 3 1 17 8 0 16 12 15 16 6
10 9 7 1 2 7 3 3 14 17 16 16 14 14 17 13 1 16 16 3
12 17 4 16 13 8 18 15 9 14 10 10 14 8 17 13 5 15 17 6
20
7 0 13 8 0 8 10 14 12 6 14 2 1 10 3 8 1 2 3 11
13 18 0 6 19 4 11 13 3 14 9 14 7 16 3 18 18 10 3 7
11 19 10 3 7 5 4 5 5 19 5 1 10 12 14 7 9 9 9 17
11 18 16 7 17 11 6 13 19 17 11 10 4 4 12 0 0 2 1 14
4 19 8 6 10 16 2 1 14 1 18 16 16 11 10 16 0 4 15 14
15 5 12 14 12 14 13 13 5 15 10 2 18 17 12 18 12 1 13 1
19 18 7 11 0 9 9 17 5 8 18 15 12 18 3 9 18 2 19 3
12 0 14 19 0 0 14 12 5 3 15 1 0 16 17 1 9 13 16 7
2 6 10 2 5 6 8 5 14 8 3 15 13 15 11 18 11 3 11 6
13 8 15 2 14 2 10 1 3 4 13 17 12 3 16 7 15 3 8 14
4 16 14 13 19 11 17 12 8 4 5 8 19 18 18 16 13 0 7 3
12 6 7 15 16 18 17 7 17 11 8 3 6 16 2 4 5 15 5 9
17 0 10 6 2 7 15 11 15 17 10 17 13 12 4 14 15 10 1 13
9 2 17 17 0 5 11 4 17 19 1 14 12 6 10 6 13 18 0 13
13 12 16 14 15 17 18 3 12 10 2 5 2 13 15 16 1 5 10 15
6 10 17 12 13 7 7 13 10 1 5 16 14 18 6 4 18 5 7 13
14 0 19 0 16 10 1 0 2 16 14 0 5 17 8 14 18 12 1 0
5 17 17 2 16 14 0 0 8 11 19 18 6 13 7 17 10 14 15 11
18 2 1 3 0 2 4 4 10 14 13 0 5 9 10 17 6 13 4 5
1 19 4 1 8 10 10 8 17 2 19 0 6 8 6 18 4 7 12 14
20
17 0 10 2 5 5 5 10 14 12 10 1 2 17 15 11 13 19 14 10
18 10 12 2 6 0 6 7 10 3 11 19 3 10 7 13 17 12 1 4
9 12 3 1 17 12 14 16 13 11 17 16 3 15 8 9 3 4 19 9
17 17 18 15 15 12 0 8 4 7 3 2 7 15 3 14 16 11 10 13
8 15 9 14 9 16 5 15 17 14 17 3 15 13 2 2 2 18 6 0
6 6 12 19 18 8 12 18 16 15 2 14 16 3 8 11 15 7 8 10
13 10 2 2 18 11 19 18 15 5 9 15 5 1 6 14 14 13 4 14
13 15 9 15 4 3 4 17 1 15 10 6 3 12 18 3 0 11 10 0
6 4 17 7 9 6 15 7 10 9 5 10 16 3 14 17 2 9 7 5
15 1 15 6 16 17 17 9 12 1 2 1 19 10 12 4 15 17 15 12
16 0 2 17 1 17 11 5 5 11 16 0 14 1 0 4 12 15 3 9
11 6 1 7 9 17 10 7 14 7 6 12 7 2 12 9 19 10 2 4
17 10 15 17 19 18 17 7 18 3 19 6 5 10 13 5 18 12 9 0
14 7 18 14 2 12 4 9 12 15 8 6 12 17 8 8 3 16 3 6
15 18 18 13 5 6 17 3 6 16 19 18 1 18 19 4 9 7 7 18
14 9 16 3 12 6 4 8 5 9 10 19 7 6 13 15 16 8 15 8
17 7 14 9 11 11 14 1 1 17 0 14 3 7 14 19 12 18 19 17
13 2 11 11 0 8 15 8 4 11 10 15 7 15 11 4 1 5 4 8
11 13 4 11 4 6 13 4 14 0 14 6 6 3 6 15 5 14 13 13
13 8 8 4 3 0 16 5 1 3 2 17 0 10 5 6 2 19 1 19
20
0 11 10 17 3 1 14 13 13 5 11 13 6 3 1 17 0 16 7 17
17 14 5 8 3 4 19 7 14 17 0 14 5 3 19 18 14 4 9 19
15 14 12 12 16 15 11 10 16 0 4 0 14 12 3 11 19 10 4 4
1 15 1 8 10 11 17 3 0 10 19 18 15 11 8 2 2 5 9 5
13 14 13 19 3 18 13 2 14 8 11 15 16 19 2 17 7 19 3 2
8 3 6 19 1 7 10 16 0 19 13 12 11 12 4 14 7 3 12 9
3 8 5 7 9 17 17 7 2 15 16 10 2 6 18 10 18 4 3 17
5 5 5 17 14 0 2 3 19 4 0 13 12 0 6 6 12 3 0 14
18 6 15 13 14 5 18 12 6 12 19 4 10 3 13 17 7 3 8 7
9 10 0 1 18 8 4 16 17 9 18 15 12 6 11 0 0 11 1 8
18 2 12 10 5 18 13 8 6 16 6 16 7 1 18 14 17 12 18 12
15 7 0 1 9 0 19 3 5 8 4 10 18 3 19 13 7 4 18 6
13 10 2 0 2 11 7 18 18 2 18 2 9 19 16 10 14 15 10 12
4 1 13 3 12 19 1 4 2 19 16 5 10 16 5 14 19 0 12 3
0 17 11 19 12 13 2 0 3 2 10 11 17 3 10 1 8 2 6 2
12 1 2 0 13 7 13 13 5 16 1 19 1 19 10 7 18 4 14 13
3 11 3 14 13 9 2 17 16 10 13 0 17 17 18 3 3 12 6 15
3 0 2 9 10 4 1 18 6 6 16 5 4 15 12 13 2 7 3 13
11 5 12 19 12 5 3 14 10 3 6 15 10 18 10 10 15 10 18 4
9 9 14 0 6 18 7 5 1 15 12 1 7 2 6 15 8 3 17 14
20
10 0 11 12 18 16 1 13 19 1 6 11 4 12 4 10 8 13 2 12
9 11 16 5 19 12 18 13 13 4 13 17 18 18 10 10 14 10 1 1
14 18 4 10 7 18 0 0 1 11 2 15 11 13 19 8 2 13 12 18
3 5 10 11 11 10 19 12 11 6 18 13 12 1 8 16 6 12 6 19
19 9 19 0 8 2 16 12 3 19 18 15 10 10 1 6 3 5 4 16
6 16 2 18 12 16 14 11 15 1 8 2 3 2 7 0 5 2 3 17
16 14 14 0 10 15 6 16 11 19 6 16 3 10 9 7 17 18 12 4
7 7 3 1 16 3 6 16 7 11 4 19 6 16 2 3 6 6 9 15
12 14 4 8 9 1 10 0 10 7 19 12 15 2 2 5 18 7 11 2
9 19 2 13 10 10 3 16 6 0 19 8 7 19 18 1 11 15 7 4
12 7 14 17 6 4 7 19 9 15 9 10 8 5 14 15 16 14 11 15
6 12 2 7 11 2 5 15 18 13 0 6 13 11 4 19 14 13 10 12
4 3 18 18 13 5 13 17 2 15 19 14 5 0 17 0 12 3 14 13
4 1 5 4 6 16 14 6 9 3 19 19 18 10 5 1 18 10 19 6
5 13 12 10 6 18 7 4 19 1 0 6 14 8 8 13 9 1 4 19
13 17 10 16 7 16 16 15 5 4 11 1 7 7 4 10 11 6 10 13
10 15 17 12 11 12 15 1 7 2 13 10 15 2 11 1 17 3 9 15
2 12 3 12 7 2 4 18 18 10 5 11 5 15 0 14 5 1 5 15
5 0 15 10 17 1 5 5 1 14 13 10 12 2 14 14 11 14 9 13
10 8 10 1 9 18 5 0 18 5 3 11 2 19 6 4 6 13 11 7
20
19 13 5 9 18 10 4 2 6 16 5 11 2 2 3 3 5 14 2 1
18 4 19 8 1 14 16 2 2 13 5 3 18 8 1 14 16 17 4 10
9 10 0 12 5 5 17 1 4 0 6 12 7 1 13 18 17 12 15 8
19 13 8 2 13 4 14 9 11 12 7 0 8 14 9 5 2 8 2 10
6 7 5 4 14 17 8 9 15 14 14 19 13 13 2 13 14 14 6 13
15 2 13 12 14 1 12 16 4 3 11 12 13 6 2 3 10 19 9 16
17 1 16 16 14 12 5 10 14 3 13 5 7 7 15 11 12 3 4 8
13 16 7 7 3 4 11 7 1 7 2 16 7 7 7 11 2 17 6 12
16 14 9 8 19 3 1 6 0 2 12 19 5 17 10 11 12 16 12 4
5 6 4 0 6 13 1 10 3 19 17 11 17 2 17 5 16 19 14 1
7 14 3 3 14 18 15 18 10 14 17 2 13 7 9 14 18 16 4 14
9 16 5 10 2 19 2 0 6 6 8 14 13 9 14 11 5 5 10 8
2 6 1 12 1 10 15 9 2 9 7 12 1 13 3 9 12 0 15 3
7 14 5 10 18 10 2 0 3 10 5 3 13 19 5 5 9 18 19 13
9 4 1 18 19 8 5 17 15 10 16 19 15 15 17 8 8 9 18 8
0 18 12 15 5 10 0 19 16 14 12 14 6 6 9 13 17 16 19 11
14 13 5 4 8 7 13 11 19 10 15 8 12 11 18 18 1 14 9 8
16 14 4 7 19 8 9 11 11 8 5 14 10 6 17 12 1 7 5 8
2 6 9 5 1 16 0 0 16 1 8 3 18 2 16 16 19 14 0 17
1 16 1 8 9 16 14 6 17 14 3 16 6 3 5 13 17 14 2 13
20
8 5 14 8 8 13 4 9 13 14 4 13 5 11 5 15 2 2 9 13
16 0 16 6 17 12 8 18 4 1 3 5 6 2 4 3 18 13 16 14
16 12 9 15 6 15 6 13 10 2 10 14 2 8 7 16 15 16 18 0
16 10 16 14 17 0 3 1 15 18 4 4 8 15 1 3 11 13 11 11
12 1 6 16 2 2 16 8 3 15 1 8 15 15 9 4 9 15 4 16
14 4 10 5 9 18 14 16 7 10 18 13 8 7 13 6 12 12 4 17
9 19 2 17 7 7 15 14 9 18 12 11 16 19 13 19 9 17 8 15
3 13 17 15 5 15 17 8 19 9 14 16 3 14 14 9 9 19 14 4
9 7 12 14 14 8 11 3 13 6 11 16 11 17 9 13 0 0 9 0
9 14 12 11 19 14 18 15 11 16 16 2 11 12 7 8 8 6 7 4
19 1 6 19 19 14 3 4 10 7 14 2 11 9 7 18 11 1 7 15
10 2 8 10 8 19 17 15 17 10 9 7 19 13 14 19 6 3 2 6
10 7 0 14 10 12 9 3 15 19 0 19 11 1 9 7 9 5 5 0
15 13 19 18 18 3 0 11 4 14 13 17 16 2 16 14 6 17 10 3
3 13 6 16 19 2 3 14 3 18 11 12 7 8 9 0 6 6 8 10
14 5 7 1 13 14 7 16 1 15 10 14 6 13 5 14 5 15 7 5
16 1 1 17 2 13 11 2 13 6 2 18 11 15 8 13 7 10 9 1
11 8 15 1 2 15 11 19 3 1 3 0 1 19 17 14 2 9 14 18
5 7 19 16 11 6 10 2 0 2 1 15 1 6 14 13 3 14 1 3
10 10 10 2 10 13 11 10 7 15 18 16 1 1 15 8 14 7 3 16
20
19 4 1 2 8 16 6 8 14 4 17 3 1 1 14 6 15 9 14 6
14 5 0 19 10 10 16 8 1 8 0 4 12 11 4 4 16 4 3 12
6 16 0 5 11 1 8 12 0 11 5 7 9 4 19 17 10 16 19 12
9 14 7 0 12 16 16 18 6 4 8 18 2 9 4 6 14 5 0 1
2 6 6 5 0 8 7 6 17 17 3 4 2 6 11 13 18 19 15 9
18 3 10 12 4 0 15 9 0 4 3 4 2 3 9 15 2 3 13 5
14 0 17 9 4 19 2 9 18 18 1 16 15 14 9 9 9 2 16 8
11 15 4 9 1 4 11 2 7 7 0 17 0 10 11 13 11 17 5 12
13 19 0 16 8 17 1 3 3 13 16 13 15 12 16 15 11 18 2 8
8 11 9 1 1 19 1 1 2 16 16 3 2 4 8 5 11 1 0 4
8 10 11 16 3 12 12 13 2 11 1 14 3 10 11 2 12 14 13 8
17 6 12 4 10 15 2 14 11 13 1 1 15 12 10 12 19 2 11 10
4 11 4 8 7 12 18 2 6 0 4 17 0 6 5 1 14 9 10 11
0 6 7 9 14 18 9 9 10 17 18 13 16 4 1 4 7 7 4 9
11 11 1 5 12 11 0 19 13 13 19 11 17 14 8 5 19 18 6 16
10 4 15 0 1 17 13 8 8 6 9 2 10 19 14 1 8 10 15 17
18 5 14 3 7 4 18 15 6 10 1 3 17 15 8 11 7 6 13 17
15 7 19 18 4 11 8 18 14 19 1 14 12 13 18 14 11 4 13 18
5 0 8 19 3 9 7 12 16 7 18 10 16 18 1 0 19 1 13 1
17 3 9 7 2 14 0 0 4 18 1 2 14 12 17 4 2 12 13 15
20
10 6 18 4 2 10 18 16 2 8 13 9 4 8 3 8 3 8 8 0
7 3 16 3 0 5 15 0 6 13 15 5 8 8 5 11 0 10 2 19
14 1 1 9 3 13 14 4 18 2 16 19 6 10 18 4 7 7 19 18
15 16 14 11 9 11 13 14 18 7 6 10 9 1 13 19 9 6 2 17
11 5 3 0 0 3 5 0 11 10 18 12 13 19 9 13 13 0 18 15
19 6 9 7 10 2 2 3 10 2 12 13 5 2 4 2 1 12 1 4
13 2 19 18 15 15 2 14 11 13 19 16 8 16 15 7 10 16 17 1
10 9 6 17 2 2 4 13 15 6 17 4 14 12 19 18 18 17 3 5
1 3 17 10 17 7 5 13 15 12 17 4 3 11 5 12 16 11 3 15
18 9 9 2 16 11 10 0 15 18 14 5 18 6 1 14 4 6 9 15
13 8 15 8 17 18 17 12 4 1 3 13 15 11 10 13 7 15 7 4
5 11 18 13 19 12 12 2 4 9 5 15 18 3 11 16 8 15 1 1
12 6 8 13 9 18 8 14 11 0 7 13 13 9 0 12 17 4 3 6
8 16 0 18 13 3 10 10 16 16 0 11 13 19 15 3 17 2 16 9
13 6 10 5 9 5 5 16 0 18 12 18 0 17 3 11 4 2 2 3
5 19 4 3 11 12 7 7 1 19 4 2 8 10 14 1 9 14 15 15
1 17 16 9 10 17 17 11 14 11 8 7 15 15 15 17 9 5 4 5
4 4 13 4 14 5 0 13 9 16 8 0 18 9 17 1 18 11 14 15
6 4 6 13 2 6 16 10 8 2 1 3 9 17 12 17 19 3 4 15
15 0 4 3 2 19 17 7 6 16 16 14 7 17 3 15 6 10 11 2
package day24_3006;
import java.util.Scanner;
class MyQueue{
private int front, rear, max, cnt;
private int[] q;
public MyQueue(int a) {
// TODO Auto-generated constructor stub
front = 0;
rear = -1;
max = a;
cnt = 0;
q = new int[a];
}
public boolean isEmpty() {
return cnt == 0;
}
public void enqueue(int a) {
rear = (rear + 1) % max;
q[rear] = a;
cnt++;
}
public int dequeue() {
int a = q[front];
front = (front + 1) % max;
cnt--;
return a;
}
}
public class path_finding_puzzle {
static int n;
static int[][] map, d = {{-1, 0, 1, 0}, {0, 1, 0, -1}};
static boolean[][]visit;
static MyQueue qx, qy;
private static boolean BFS(){
qx = new MyQueue(n * n); qy = new MyQueue(n * n);
qx.enqueue(0); qy.enqueue(0);
visit[0][0] = false;
int dx, dy, x, y, w;
while(!qx.isEmpty()){
x = qx.dequeue(); y = qy.dequeue();
w = map[x][y];
for(int i = 0; i < 4; i++){
dx = x + w * d[0][i];
dy = y + w * d[1][i];
if(dx >= 0 && dy >= 0 && dx < n && dy < n && !visit[dx][dy]){
visit[dx][dy] = true;
qx.enqueue(dx); qy.enqueue(dy);
if(dx == n - 1 && dy == n - 1) return true;
}
}
}
return false;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner sc = new Scanner(System.in);
int testcase = sc.nextInt();
for(int tc = 1; tc <= testcase; tc++){
n = sc.nextInt();
map = new int[n][n];
visit = new boolean[n][n];
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
map[i][j] = sc.nextInt();
}
}
if(BFS()){
System.out.println("YES");
}
else System.out.println("NO");
}
}
}
Editor is loading...