Crazy King
quoc14
c_cpp
5 months ago
56 kB
2
Indexable
DFS and BFS
Level 4
Crazy King
King Peter lives in kingdom A, and his daughter in kingdom B. King received a letter telling that her daughter gave birth to a child. King is incredibly curious to see his grandchild! Unfortunately that’s not gonna be that easy.
Kingdoms A and B are separated by a forest. There are lots of enemies in the forest, and King is not that curious to see them. If they attack king on his way to kingdom B, then he will never ever see his grandchild and daughter again because of lethal consequences.
Security Council of the King disposes information about location of the enemies, which makes the things easier for king. For some unknown reason a forest is MxN chessboard. (N is the number of rows, and M is the number of columns). N,M <=100 are positive integers.
Enemies of the King can ride horses as showed in the picture. Usually horses ride (or jump) that way in Chess. Unfortunately king can’t take an airplane from point A to point B because it is not invented yet. So he moves the same way as chess-king does (refer to picture for details).
King can’t move to a square X, if a horse of the enemy is on that square. While the king is moving horses are not, but if at least one horse can reach square X in one move, then king can't move to that square (except for the case when square X is either kingdom A or B).
You are the chief of Electronic Intelligence department of kingdom A (by the way the computers are already invented). And you’re asked to find the length of the shortest route L from kingdom A to
B, as king can’t wait any longer.
Input
The first line of input contains the number of tests T <=100. The first line of each test contains 2 numbers M and N. Then M lines follow each containing N symbols from the set S = { ‘.’, ‘Z’, ‘A’, ‘B’}. ‘.’ means that square is not occupied. ‘Z’ - horse occupies that square. ‘A’ - kingdom A, ‘B’ - kingdom B. Each test contains exactly one kingdom A and B.
Output
Find number L for each test and print line L if King can reach kingdom B. Replace L with corresponding number. If King can’t safely reach the kingdom B print line -1.
Sample
Input
4
5 5
.Z..B
..Z..
Z...Z
.Z...
A....
3 2
ZB
.Z
AZ
6 5
....B
.....
.....
..Z..
.....
A..Z.
3 3
ZZ.
...
AB.
Output
-1
2
-1
1
1
4
1
2
3
2
2
2
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
Time: 0.078000000 s.
20
5 5
.....
.....
A....
BZ...
.....
5 5
B....
.....
....A
Z....
.Z...
5 5
.....
.A...
BZZ..
Z....
.....
5 5
Z....
B.AZ.
..Z..
...Z.
Z....
5 6
A....
.....
....Z
B....
.....
.....
6 8
.A....
......
B.....
......
......
.Z....
.Z.Z..
..Z.Z.
5 7
.....
Z....
A...Z
Z.B..
.Z...
Z....
..Z.Z
8 5
........
......Z.
.....A.Z
.......Z
...BZ...
48 57
Z..ZZ............................ZZ.............
.....ZZ...Z.....Z..........Z.Z....Z.............
.....Z.Z....Z.Z...Z.......ZZ........Z...........
........Z............Z.Z....Z..........Z....ZZ..
.Z........ZZ...Z..............Z.............ZZ.Z
Z..Z...Z..........ZZ..ZZ..ZZ......Z..Z....Z.Z..Z
..........ZZ...Z..........Z.Z..........ZZ.......
......Z....Z..Z......Z...Z.Z........Z..Z...Z....
.Z.........Z.Z.......Z...........Z.......Z.Z....
......Z............Z...Z............Z....ZZ....Z
.......Z........Z.....Z........Z.Z.Z.....Z...ZZ.
.Z.............Z.Z............Z.....Z...Z..Z..ZZ
......Z......Z.........ZZ.Z.Z....Z......Z.......
...........ZZ.........Z........ZZ..Z.Z....Z..ZZ.
...Z..Z................ZZ........Z..Z.....Z.Z...
....ZZZ....................Z..........Z.Z.......
...Z....Z..ZZ...Z.Z..Z............Z......Z......
...Z...................ZZ..Z.....Z..............
......Z.....................Z.......Z........Z..
.....Z............Z..Z...Z.....Z.Z......Z....Z..
...Z...Z.Z..........Z......Z........Z.......Z..Z
..............Z..............ZZZZZ.........Z....
....Z...Z....Z.....Z...............ZZ...ZZ......
..Z.ZZ......Z..............ZZ..Z................
........Z.ZZ.Z..Z...ZZ.........Z.Z.ZZ.......Z...
....Z......Z..Z..Z.....ZZ.Z....Z........Z.Z....Z
...Z.......ZZZ...............Z.......Z.ZZ..Z...Z
...Z....Z.....Z....Z..Z........Z.....Z...Z...Z..
......Z.......ZZ............Z..Z......Z....Z...Z
..Z..Z....Z...........Z..Z.Z......Z.ZZ.....Z....
.......Z............Z.Z.........Z......Z......Z.
...Z.......Z.ZZ.......ZZ...Z.ZZ......Z........Z.
........Z.............Z...............A.....Z...
.............Z..Z...............Z.Z....Z...Z.Z.Z
......Z...Z..Z...Z.......Z..ZZ.....Z.......Z....
........Z..ZZ....Z........Z.Z.....Z.....Z..Z.Z..
ZZ...................ZZZ.ZZZ.Z........Z..Z......
........Z....Z.Z........Z.Z......Z..............
.........Z..................Z.....Z........Z....
......ZZ............Z......Z...Z...Z...Z..ZZZZ..
.........Z.......Z..Z...Z......Z.Z.Z..Z....Z....
........Z....Z....ZZ.............ZZ........Z.Z..
Z......Z................................Z...Z...
..Z...Z..............Z..............Z....Z.....Z
.......Z....ZZ.Z........Z..Z...................Z
.Z....Z......Z.Z.....Z..ZZ.Z............ZZ......
..ZZ................ZZ.Z...Z......Z.Z...........
....Z.Z...Z..Z..........Z..........Z....Z..Z....
......Z....ZZZ..............Z..ZZ........Z...B..
..........Z.Z.Z.Z...Z.Z.........................
...ZZ........................Z.......ZZ....Z..Z.
.Z.ZZ........ZZZ...ZZ...Z............ZZ.........
Z.....Z.....Z........Z.....ZZ........Z..ZZZZ....
..........ZZ..........Z..Z...ZZ.Z...............
...........Z.....Z.Z....Z.....ZZ...........ZZ...
Z.....ZZ...Z..Z......ZZ......ZZ.................
.ZZ.......ZZ....Z...Z...............Z...Z......Z
27 49
..................ZZ....ZZZ
Z.....Z..Z...Z.....Z......Z
............Z...Z..ZZ......
......Z....Z.............Z.
............Z.....Z....Z...
....Z........Z..Z.........Z
......ZZ.............Z.....
Z........Z....Z......Z.....
ZZ...........Z.............
.Z.Z.....Z.......ZZ....ZZ..
.Z.Z....Z..Z...Z...........
...................Z.......
.Z......................ZZ.
............Z....Z.....ZZ.Z
..........Z..............Z.
.......................ZZ..
..Z..Z......Z...Z..........
...................Z.......
Z.Z..Z.....ZZ..Z........Z..
Z..Z.....Z...Z.....Z..Z....
....................Z......
.Z...................ZZ....
.........ZZ.....Z.....Z....
...Z.Z.....................
Z..Z..Z..Z.Z........Z...Z..
...Z.............ZZ........
..................Z.Z..Z...
ZZ.........Z...........Z...
.......Z..Z.Z.........Z..Z.
.....ZZZ...Z.....A...Z.....
.............Z....Z..Z...Z.
.Z.Z.ZZ...Z....ZZ........Z.
...Z..ZZ..Z....ZZZ.......Z.
..Z.Z......Z........Z......
...Z.Z...Z.................
.........Z........ZZ..Z....
............Z....Z...Z.....
..Z.Z........Z...Z.........
ZZZ......Z.Z...Z......Z....
...Z.............Z.........
.Z............Z..Z.....Z...
.........................ZZ
......ZZ........Z..ZZ.Z....
....Z.......Z..Z..........Z
..........................Z
ZZZ.........Z....Z.Z..Z..Z.
........Z...........Z......
.Z.Z............Z.......ZZ.
..ZB...Z............Z......
17 30
...Z.......ZZ.Z..
...........Z.....
.......Z.Z.......
...ZZ............
......Z..Z.......
...........Z.....
.Z.Z......Z.....Z
....Z......Z.....
................Z
..........Z..B..Z
.......ZZ.Z......
Z.....Z.....Z....
..........Z....Z.
.Z.Z....Z........
................Z
.Z.....Z.Z.....ZZ
.........Z......Z
........Z........
.................
.............Z..Z
Z..Z..Z..........
.................
.Z.ZZ............
.............Z...
..........Z.Z.Z..
....Z.Z.Z.Z....Z.
..Z.....Z..Z.....
..............A..
...Z........Z.Z..
.Z.........Z.....
45 66
Z..Z......Z......Z...ZZ..Z......Z...ZZ.Z.....
Z.......ZZ........ZZ.ZZZ........Z.....Z....ZZ
....Z.........Z.Z......Z.....ZZ.........Z....
.....................Z.......Z..........Z...Z
........Z...................Z................
....Z...Z...........ZZ.........Z.....Z....Z.Z
....Z..........ZZ..............ZZ.....ZZZZZZ.
..Z.Z.........Z.Z........Z........Z..Z..Z..Z.
...ZZZ.ZZ....Z...ZZ....Z.ZZ.........Z.......Z
......Z...Z.....ZZZ...ZZ................Z....
...Z.......ZZZ...Z...................Z.......
Z...Z...........Z...Z..Z.Z................Z..
.....................Z....Z............ZB...Z
.Z.Z..............ZZZ.....Z...Z..........Z.ZZ
...........Z.......ZZ..........Z...Z.........
...Z...............Z..ZZ..............Z..Z...
.............Z.......ZZ....ZZZ.Z..Z.....Z...Z
.....Z..........Z....Z..Z.......Z............
...........Z..............Z..........Z...Z...
....Z.......Z.Z........Z.....................
..........Z.........Z..ZZ.Z............ZZ.ZZ.
.Z......Z.Z.....Z.Z.Z..Z.....Z..............Z
Z.............Z................Z.............
Z....ZZ.ZZ.Z......Z.....Z........Z...........
..Z.......Z.....Z...Z....ZZ.............Z....
............Z...Z...ZZ.......................
....Z....................Z.Z...Z..Z......ZZ..
.Z.......Z....Z....Z......Z............ZZZZ..
....Z.Z....ZZ...Z.........Z....Z.....Z.......
.Z...........ZZ......Z......Z................
.....Z.Z....Z......ZZ....ZZ.......Z......Z...
.......Z..........Z.....Z....ZZ.........Z....
....Z....Z..ZZ.......................Z.Z.....
.........ZZ.................Z...Z..ZZZ.......
.Z..Z......Z........Z.................Z......
..Z..Z...Z....Z......Z..............Z..Z.....
....Z..Z..Z..Z..Z........Z...Z.Z..ZZ.......Z.
Z.Z.ZZ.........Z............Z................
ZZ.Z....Z.A........Z....................Z...Z
.....Z........ZZ......ZZ......Z.......ZZ.....
......Z..ZZ.....................ZZ......Z...Z
......Z....Z.........Z.Z..........ZZ.....Z...
......Z...Z.ZZ...................ZZ..........
.Z..............Z..Z..Z.ZZ....ZZ...Z..Z...Z..
.ZZZ.....Z.................ZZZ.............Z.
.......Z......Z...ZZ.Z.......................
Z.Z.....ZZ...................Z..........ZZZ..
.......Z......Z...Z..........Z.Z...Z......ZZ.
Z..............Z.......Z.............Z.Z.ZZ..
Z...Z........Z..........Z.............Z....Z.
....ZZ..Z.....Z..ZZZ........Z.........Z.....Z
Z.Z.Z.Z.....Z.Z..Z....Z..........ZZ..........
.........Z............Z.Z....Z.Z........Z....
.Z...........ZZ..Z..........................Z
................Z.....Z....Z..............Z.Z
.....Z......Z.Z............Z.......Z.Z.......
......Z.............Z.........Z......Z..Z....
..Z..........Z....ZZ..............Z.......Z..
..Z....Z.................................Z...
.....................ZZ.......Z............Z.
Z...........Z.........ZZ...Z............ZZ...
..ZZZ..........ZZ............Z..........Z..Z.
....Z.....Z......Z.Z...Z....Z................
..ZZ..............Z.......ZZ..Z............Z.
.....Z.....Z........Z....Z...........Z.......
.....Z..Z....Z...Z..Z..Z.....................
49 37
....Z..Z...ZZ..Z...Z........ZZ........ZZZ.ZZ....Z
........Z...............Z........................
...Z.Z.......Z.Z.............ZZ.....Z....ZZ....Z.
...Z.......Z..Z.Z..........Z..Z......Z...........
.Z........Z..Z.........Z.Z....Z...Z....Z...Z.....
.....ZZZ.Z....Z..........Z.Z.....Z........Z......
Z.Z...Z..............Z.........Z.................
.......Z.........Z.......Z...ZZ.Z............Z...
..Z........Z.Z.....Z..Z.......Z.Z................
.Z...Z......Z.ZZZ....Z.......Z....Z..............
....Z.......ZZZ....Z.Z.....Z...................Z.
........ZZ...Z.Z.Z...........Z..Z......ZZ........
ZZZ.Z....Z....Z.....................Z............
..Z........ZZ.ZZZ.Z............Z....ZZ..Z.....Z..
.Z...Z.Z.....ZZ.........Z...Z........Z.ZZ......Z.
.Z..............Z.Z..Z.........Z..Z.ZZ.Z.Z......Z
.......Z......Z.ZZ......ZZ..Z......Z...ZZ.....Z..
....Z................Z..................Z..Z....Z
....Z......Z...Z.ZZ....ZZ.Z.Z.....ZZ......Z.ZZZ..
...........Z...............Z.....Z..Z..Z.Z......Z
..Z.ZZ....Z.........................Z.........Z..
Z.....Z.Z...Z..Z...Z.............ZZ...Z...Z...Z..
........Z..Z..ZZ............Z....Z.Z....Z......ZZ
...Z......Z..Z....ZZ.....Z........Z..ZZZ........Z
.............Z.....Z.............Z........Z.Z....
...Z.Z.Z.Z..Z.ZZ.Z..............Z..Z......B......
.Z.....Z.........Z..Z............................
..Z.......Z............ZZ....Z.Z.Z...............
..Z.Z.........Z.......Z...............ZZ......Z..
Z......Z....ZZ..ZZ.Z......Z.......Z....Z.Z...ZZ..
...............Z.............ZZ.Z.......ZZ.......
......Z..Z.....Z.............Z.........Z.....Z...
.Z.A.....ZZ................ZZ.........Z...Z......
..........Z.......Z........Z........Z.Z..........
.............Z..Z..Z.........Z...Z..Z..........Z.
.....Z.............ZZ.........ZZ.....Z..Z..Z.....
.............Z..Z.....Z.......Z.........Z...Z...Z
75 39
ZZ.Z.....ZZ.............Z.Z.......Z.Z.................Z.......ZZ....Z...Z..
....Z.....ZZZ...Z.....ZZ...............ZZ.Z........Z...............Z.....Z.
.......Z...Z...........Z...Z..ZZ....Z..................Z........Z.....Z..Z.
............Z.....Z.Z.Z...Z.ZZ.........Z....Z.......Z............Z..ZZ..Z..
..Z............Z.................................Z...ZZZ..Z.....Z...ZZ.Z...
...ZZ..Z.....................Z..........Z.................Z....ZZ...Z......
....Z...Z.....Z...............ZZZ...Z..........ZZ.....Z.......Z..Z......Z..
.........Z...Z..Z..............Z..Z.ZZ...BZ..ZZ..Z...Z.Z........ZZ...Z....Z
..........Z.............................Z...Z...Z......Z.........ZZ.ZZ....Z
......Z.............Z...........Z......................ZZ..............Z...
..Z.Z.Z...........ZZZ.Z.........Z..Z....Z......ZZ................ZZZ.Z...Z.
...Z......ZZZ..............Z......Z.Z....Z.....Z........ZZ...........ZZ..Z.
Z..ZZZ.......Z..Z...............Z.............Z.Z......Z...Z...Z..Z..Z.....
...........Z..Z..Z...Z.Z........Z..........Z..............ZZ.Z...ZZ....Z...
Z.Z...........Z.Z.Z.............Z.Z..Z.ZZ.Z.Z..........Z.ZZZ.......Z.....Z.
........ZZ.............Z................Z........Z.....Z.............Z.....
.....Z.......Z.ZZ.Z.Z.....Z..Z.........Z.Z.......Z....Z.....Z...Z........Z.
.ZZ.....Z..Z..Z...........ZZ.Z.Z.......Z............Z.Z..........Z.........
....Z..Z.....Z..........ZZZ...Z.ZZ.....Z........ZZ.........Z..Z............
......Z.....ZZ.Z...Z..Z....Z.....Z.....ZZ...............ZZZ........Z.ZZ....
Z....Z..........ZZ........Z....Z....Z.......Z.....Z..Z....Z.....Z........ZZ
.....Z........Z...........ZZ.....Z..AZ.Z....Z...........ZZ..Z......Z.Z.....
.......Z...Z........................Z..Z....Z........Z.Z.......Z....Z......
Z.Z..ZZZZ........................ZZ..ZZ..Z.............Z.Z....Z...Z.Z...Z..
Z....Z....Z.......Z.......Z.....ZZ..Z...Z..Z..........Z.........ZZ....ZZZZ.
.....Z..Z...............Z.........................Z.Z...........Z........Z.
......................Z.Z..................Z..Z.Z........Z.ZZ........Z.....
........Z.....Z.Z......Z...Z.....Z..Z.......Z.............Z...Z....Z.......
.Z....Z.......Z...........Z.Z...............Z..Z.................Z.....Z...
...Z.....Z....ZZZ.Z....Z.Z.Z.....Z.Z...Z......ZZ.Z......Z...Z..............
......ZZ.....Z..Z.Z...Z..Z......Z.ZZ.......Z.............Z.Z...............
..ZZ......Z.Z.Z...........ZZZ............ZZZ...Z..ZZ.......Z....Z.ZZZ..Z...
........Z.....................Z.....Z..Z....Z...............Z............Z.
.....ZZ...ZZ...Z................Z.Z...Z..................Z.Z.........ZZ..Z.
...Z................Z....Z..Z.ZZZZ..Z...Z....Z....Z.....Z..Z..Z...Z...ZZ...
Z............ZZZ....Z.........Z........Z..ZZ........Z.Z...Z..Z.....Z....Z..
....Z.ZZ......Z.Z.......Z.......Z....Z........................Z..Z...Z.ZZ..
Z.......Z.......Z............Z........Z..Z..Z.......Z..Z.....Z.Z........Z.Z
Z.Z..ZZ.........ZZZ.........Z......Z.........Z......ZZ...Z.....Z..Z....ZZ..
79 72
Z.......Z...Z...Z..Z.Z.....................ZZ..........ZZ.........Z............
....Z....Z..Z..........Z....Z..Z..Z.......Z.Z.Z.............Z......Z...........
...Z............ZZ.Z................Z..Z..Z...Z...Z.Z.Z.Z......Z...Z...........
..Z...Z.............................Z...Z.....Z..Z.Z...Z..Z.Z.Z.Z..Z..Z...Z....
.Z.......Z...................Z......Z.......Z...........Z..........Z...........
.Z..................ZZ..ZZZ...Z..Z.ZZ.Z.............Z.....ZZ.............ZZ....
Z.A.Z.Z.Z..Z....Z...Z.......Z........Z..........Z....Z....Z...ZZ.Z.............
....Z.....ZZ...............Z.Z..........Z..Z.......Z.............ZZ...Z........
..Z..Z...Z.ZZ..Z.....................ZZ..................ZZ..Z.ZZ.Z......ZZ....
Z....Z........Z...........Z..Z......ZZ................Z.Z......Z.......Z.......
..Z...ZZ.Z.........ZZ.Z..............Z.Z........Z.....ZZ....Z.....Z.Z..Z.......
....Z.................Z....Z..Z..Z...Z.......Z......................ZZ......Z..
......ZZ.Z...Z.Z....Z..........................Z.....Z...Z.............Z.Z..Z..
........ZZ.......Z.....Z.Z.Z...B.......Z...ZZ.....Z.Z..Z...Z...ZZZ..ZZ...Z.....
.....Z.........Z.......................Z.........ZZZ...........................
....Z.....Z.......Z........Z.......Z..Z............Z.Z...ZZ..ZZZ..Z.........Z..
........Z..Z.......ZZ.Z.Z..Z.Z....ZZ...............ZZ.......ZZ....Z.....Z......
.........ZZ......Z....Z.....Z...........Z.....Z.......Z...........Z............
....Z..........................Z.Z......Z......................ZZ.....Z........
........Z...Z.........Z......Z.Z.....Z.....Z....Z...Z....Z.............Z....Z..
..Z..Z.........Z.Z.......Z........Z..........Z...ZZ.Z......Z.......ZZ..........
....Z.Z...Z..........Z..Z........................ZZ....ZZ.Z...................Z
...Z....Z..Z.Z...........Z.................Z............ZZ...........Z.....Z..Z
.......Z.Z...........Z.......Z......Z......Z........ZZ....Z...Z.........Z.Z....
..Z..Z.....Z..........Z.Z....Z....Z..............Z..Z...Z...Z..................
........Z...........Z.Z...........Z..Z.Z...ZZ....Z..Z...................Z......
.........Z.Z......Z....Z..........Z.........Z...........Z..............Z....Z..
.Z..Z..........Z..........Z...............Z.........ZZ...Z.Z.Z.....Z...........
...............Z.Z...Z..ZZ...Z...Z....................Z.Z.......Z..Z....Z......
......................Z...........................Z......Z..................Z..
..Z.ZZ.Z........Z...Z................Z..Z......Z............Z.......Z..........
..Z........ZZ...........Z....Z.Z....Z.........Z...Z...ZZZ.....Z....Z...........
.Z..........................Z....Z..Z...............ZZ....ZZZ....Z..Z......Z...
..........Z.........Z..Z....Z.Z................................................
.........Z....Z...ZZZ........ZZ............Z........Z.Z............Z.......Z..Z
..Z...Z...Z...ZZ..Z........Z.............Z....Z.................Z....Z......Z.Z
Z..Z...ZZ.Z............Z..ZZ..Z...Z..........ZZ.......ZZZ...Z.ZZ..Z..........Z.
...........Z.......Z....ZZ.ZZ.....Z.......Z...........Z..Z....Z.Z.............Z
.................Z..Z.ZZ........ZZ...............Z..........Z...Z.....Z........
.....Z.....Z..Z..Z..ZZ..Z......Z....Z......Z..Z.ZZ.Z.Z.......Z.Z.Z...Z.ZZ....Z.
........Z................Z.....Z..Z.ZZ....ZZ......ZZ....Z................Z.Z...
..Z.......Z..Z..Z...Z...Z...............Z.Z..Z......Z..Z...........Z...Z..Z....
ZZ......Z...Z...........Z...Z..........Z..............ZZ..ZZ.Z..........Z.....Z
.....Z...........Z....Z........Z...ZZ.....Z........Z..ZZ.....ZZ...ZZ..Z..ZZZ.Z.
.....Z....Z....Z.........ZZ..Z.Z.......Z..............Z....Z....Z.Z.Z.....Z....
.......ZZ.....Z.Z.Z.Z.Z.ZZ.Z................Z....Z.........................Z...
.Z..Z..Z.Z.........Z............Z.Z...Z........Z.ZZ..Z.Z.ZZ.Z.......ZZ.Z..Z....
....Z.......Z.................Z.................Z...........Z..........ZZ.Z....
Z.....Z.Z.......Z..Z.Z.Z..............Z.ZZ.Z.....Z..Z...Z..................Z...
..Z...ZZ.....Z............Z..Z.....Z....Z..Z..Z...Z.Z.......Z......Z.Z......Z..
.Z....Z..........Z....Z...........Z.......Z...Z.Z..............Z.Z.Z.Z.Z..ZZ...
.....ZZZ.Z..ZZ..ZZ...........Z........ZZ..Z..Z..........Z...Z....ZZ..Z.........
...........Z....Z..........ZZ.Z.............Z......Z............Z..........ZZ..
..Z....Z.Z...ZZ...............Z.Z....Z.....Z......Z.......Z......Z.............
.....Z............Z..........Z.ZZ.....Z..ZZ.Z........Z.....ZZ....Z......Z......
...ZZ....Z....ZZZ..............Z...Z.Z................Z...........Z..Z......ZZ.
.........Z.......Z.ZZ.Z.......Z.Z...Z........Z...ZZ.Z.Z...Z...Z..Z.............
......Z...Z..Z..Z.Z............Z........Z........Z..........ZZ....Z..Z.......Z.
Z............Z..........................Z.......Z.Z........Z.....Z..Z.Z.Z......
.....Z..Z.Z.......Z................Z.....Z...........ZZ........ZZ..............
Z................ZZ........Z.........Z..........Z.Z.Z...Z.......Z......Z.....Z.
...Z........Z........ZZ......Z.ZZ.....Z.......................Z.....Z...Z....Z.
ZZ.....ZZ..ZZ.................Z.....ZZ........ZZZ.ZZ..........Z..Z...Z.ZZZ.....
Z..........Z......Z............ZZ...........................Z.........Z..Z...Z.
.....Z...Z......Z........Z.........Z..........Z....Z...Z.Z....Z....Z.....Z.Z...
......Z.Z.Z.............ZZ......Z..Z...Z....ZZ.....Z................Z.Z...Z....
.........Z...Z........ZZ.Z...Z.....Z.ZZ..Z.................................Z...
..............Z...Z......Z.......Z.......ZZ.......Z......Z................Z.Z..
..........Z..Z....Z...ZZ............Z......Z......Z..Z..........Z.......Z....Z.
........ZZ..Z.....Z..........Z..ZZ...Z......Z....Z....Z...Z....................
.Z.........Z.Z.......Z.......ZZ.............Z....Z.............................
...Z.............Z...Z.Z...............Z...Z......Z......Z.........Z..ZZ.......
69 76
..Z...............Z.Z....Z.Z..............ZZ.Z.Z.Z...................
.....................................Z....ZZ.ZZ...........Z.Z..ZZ....
.............Z...Z........ZZZZ....................Z.Z.Z.........Z.ZZ.
.Z..ZZ..Z......Z..Z.Z...Z..................ZZ......ZZ..Z....Z.......Z
......Z..Z...........Z...............Z.Z.....Z.....Z..Z.....Z..Z...Z.
.....................Z.Z..Z.Z..Z.Z..................Z.Z.....Z..Z.....
.Z..........................Z.ZZ..Z..........................Z.......
.Z......Z........Z.....Z..........Z.....................ZZ...Z....Z..
.........ZZ.Z.....ZA..ZZ...ZZ..ZZ....Z.....ZZ.......Z.Z....ZZ....ZZ..
.....................Z........Z....Z..............ZZ.....Z.........Z.
..Z...Z......Z.......Z...............Z..........................Z....
..Z......Z.....Z......Z.....Z............Z...........................
Z......Z....Z.ZZ.....Z.Z......Z.....ZZ.....Z.ZZ..Z...................
Z...............Z.......................Z..Z.......................Z.
ZZ..Z.....Z.....Z....ZZ........Z..........Z.....Z.ZZ..............Z.Z
..ZZ..........Z..........Z..........Z.....Z........Z.Z.........ZZ....
Z.Z.Z..............Z..ZZ...ZZ.....ZZ.......Z..Z.Z.Z.....Z.Z.....Z....
.....Z...ZZ...........Z..Z.Z..ZZ....Z..........Z.Z...........Z.......
...Z.........Z.Z.....Z....ZZ............ZZ......ZZ.Z...Z...........ZZ
Z..Z...Z............Z........Z.Z....Z....Z...Z...Z...........Z.....Z.
.......Z...............Z...........Z...Z............Z...Z............
......................Z......Z.Z........Z..Z.Z.Z...Z...............Z.
.....ZZ........Z.Z..........Z....Z..Z.Z...Z............Z.Z....Z.ZZ...
ZZ.Z......Z..Z...ZZ....Z....Z....Z..Z....ZZ...........ZZ..ZZZ......Z.
.......Z..Z.......Z.....Z.........Z...Z..........Z................Z..
..Z....Z...Z..Z.......Z.Z........Z.Z.ZZ.......Z.....Z........Z...Z...
Z..Z........Z...........Z.Z...........Z................ZZ....Z.....Z.
....Z.....Z..Z.....Z.Z....ZZ.......Z...Z...............Z.........Z...
Z.Z...Z.Z................Z..ZZ...........Z.Z.....Z..Z...Z..........Z.
.ZZ.Z........Z............Z..ZZ...Z...Z....Z..Z.......Z.......Z...ZZ.
Z...............Z...Z........Z.............Z....Z....Z...............
.Z....Z....Z..Z................Z.......Z...............Z.Z.....Z....Z
..............................Z.................Z.Z.Z...Z...Z..ZZ....
.....Z.......Z....................Z............Z....ZZ..Z............
..Z......Z..Z........Z...Z......Z..Z.Z............Z......ZZ....ZZ.ZZ.
.Z...Z........Z.............................Z......Z..........ZZ..Z..
......Z.Z....Z..Z.Z..Z.........ZZ.Z...Z..Z.Z..............Z..........
.............Z.Z...Z....Z......Z.....ZZZ....................Z........
.ZZZZ..Z...Z..Z............ZZ...Z....Z..........ZZ.Z...Z............Z
..ZZ.................Z..Z............Z......ZZ..ZZ.Z...........Z.ZZ..
.....Z.Z..Z.........Z..Z......Z.....Z.Z.............Z......Z.....Z..Z
...Z...Z.Z.....ZZ..........ZZZZ.....ZZZ...Z.....Z......Z.Z..Z.ZZ...Z.
......Z....Z.ZZ.Z.......Z.Z...Z.Z.....Z..Z...ZZ.....Z..............ZZ
...Z.Z...ZZ...Z.....Z.....................ZZ.........................
.................Z........Z.........Z.......Z.......Z..Z.ZZZ...Z..ZZ.
.........Z.......ZZ............Z.Z.Z.Z........Z..ZZ....Z.......ZZ....
.Z..Z................Z..Z.......Z..ZZ............ZZ.Z................
......Z..ZZ.......................ZZ.Z.......Z...ZZ..........ZZ....Z.
.Z.Z......ZZ....Z..Z....Z..Z......Z..Z.Z.Z.........Z...Z...ZZZZ.Z...Z
...................Z....Z...Z........Z...............Z....ZZ......Z..
............Z..Z...Z..Z..........Z.................ZZ...Z............
.....Z..Z...........Z.........Z..ZZ..........Z............Z...Z...ZZ.
..Z..Z...ZZ..........Z..............Z....Z...............Z.Z...Z..Z..
...ZZ.ZZ............Z....Z...B...Z..............ZZ......ZZ...Z...Z...
.Z....Z......Z....Z....ZZ........Z.Z..ZZ............Z...Z.ZZ..Z...Z..
...........ZZ..............ZZ......Z..............Z.Z...ZZZZ..Z......
....ZZZ...........Z...Z....ZZ...Z..ZZ..Z..Z.........Z.....ZZ.Z......Z
Z.Z.......Z.............Z..............Z.Z...Z..ZZ............Z......
..........Z.............Z...Z........Z.......Z......Z...........Z....
..Z.......Z..........Z.Z.....Z..............Z...Z..Z.........Z...ZZ.Z
........ZZ....Z.........Z.......Z....Z.........................Z.....
Z......Z........Z............................Z.Z..ZZ.Z.....Z..Z......
.........Z....Z...........................Z......Z....Z....Z...Z.ZZ..
....Z.............Z......ZZ.Z........Z.Z....Z..Z..Z.........Z...Z.Z..
.Z.Z..Z...Z.......Z.....ZZZ...Z....Z........Z........Z...Z...Z...Z...
...Z..........Z...Z.Z....Z.Z.ZZ..................Z.Z...ZZ.Z.Z........
............Z..Z.......Z.........Z........Z.....Z.......Z..........ZZ
.Z......Z..Z.......Z..........Z.....Z...Z..ZZZ...........Z...........
...........Z..ZZ..Z.............................Z............ZZ......
.........ZZ.Z...ZZZ........ZZZ....Z.Z....Z..........ZZ..Z.....Z......
................Z..Z...........Z...ZZ........ZZ.Z.....Z.Z.....Z......
......Z.Z..ZZZ.........................Z.....ZZZ.......ZZZ...Z.Z.....
..Z..........ZZ..Z..........Z............Z....ZZZ.......Z..Z.Z....Z..
..Z..................ZZ.........Z.......Z.ZZZZZ..Z.......Z........Z..
....Z......Z...ZZ.....ZZ..Z...Z............Z.....Z...Z.Z..Z..........
.Z.Z.Z..............Z.Z.....Z.......Z..........ZZ.............Z......
89 95
.......ZZ.Z.........Z.........Z.Z..........Z.....Z.Z.Z..Z.............Z...Z......Z.......
ZZ.Z.........Z.....Z.......Z..Z....Z.......Z...Z.Z....ZZ......Z.Z........Z..Z.Z..........
Z......................Z..Z....Z............Z.Z.............Z..................Z.........
....Z.Z.Z.Z.........Z..............Z..Z........Z..........Z.Z..Z.........Z.Z.........Z..Z
.Z............Z..Z....Z....ZZ.Z.ZZ.Z.Z.........Z.......Z....ZZZ.ZZ...Z..Z.......Z........
Z....Z....ZZ............ZZ.......Z..............ZZ...Z...Z.....Z.ZZ.Z.Z............Z.....
.............Z.Z.....ZZ...........ZZ.....ZZ.....Z....Z..Z......Z...Z.Z......Z............
Z....ZZ....Z............Z........ZZ...........Z........Z.....ZZ.................Z......ZZ
........Z.............Z...ZZ.ZZ...ZZ.Z...Z......Z.Z..Z........Z.Z....Z...ZZ..Z.Z.Z.......
...........Z.Z..........Z.............Z..Z....Z.......Z......Z.Z......................ZZZ
............................................Z..Z....Z.Z........Z...Z........ZZZZ.........
............Z....Z.Z......Z.........Z.........Z.Z.............Z..Z......................Z
..........Z..................Z........Z..Z..Z........................Z.Z.......ZZ.Z......
...Z.........Z.................Z..........ZZ.Z.............ZZ...Z....ZZ..Z..Z.....Z.....Z
...Z.Z.......Z..ZZ.....Z....Z.Z.......ZZZZ...........Z..Z..Z....Z..........ZZZ.Z..Z...Z..
.Z......ZZ..Z............Z.Z.Z....Z.....Z....Z.....Z........Z.........ZZ....Z...Z.Z...Z..
.....Z...Z.Z......Z.Z...........Z.....Z...........Z..............Z...........Z..........Z
......Z.....Z..............Z.ZZ..Z...Z.............Z....Z.Z.Z......Z.....ZZ..............
Z..Z....................Z...Z............Z.......................Z.......................
.........Z........Z...Z....Z..........ZZZ.Z.................Z..........Z.ZZZ.........ZZZ.
Z..........ZA....Z..................ZZ..ZZ............ZZ........Z...Z.Z.Z.............Z.Z
ZZ.Z....Z..........Z........Z....Z..ZZ..Z...Z.Z.....Z......Z......Z..ZZ......ZZ....ZZ....
.ZZ.Z...Z....ZZZ.Z....Z...ZZ............Z......Z..........Z...............ZZ.......ZZ..Z.
.....Z.........Z...ZZZ.Z.ZZ.......ZZ....Z.....Z.Z..........Z.Z........Z.............Z...Z
.Z....Z......Z...Z.........ZZ........Z.Z...........Z..............Z.Z........Z...........
.............Z...............Z......Z.....Z..Z....Z....Z.Z..........ZZZZZ..ZZ...Z.Z......
.Z............Z....Z..Z..........Z..............Z..........Z.Z......B.......Z..Z.....Z.Z.
ZZ.......Z....Z..Z...Z.ZZZ..Z...Z.......Z....Z....Z...Z.......Z..........Z.Z.....Z.......
..............Z......Z.........Z.....ZZZZ..ZZ...Z...........Z...ZZ......Z.........Z...Z..
..Z..........................Z..........ZZ.....Z.Z.Z....Z..Z.......Z.............Z.......
....................Z............Z....Z................Z.......Z......Z.Z...Z..Z....Z.Z.Z
.....................Z.ZZ...ZZ.Z.....ZZ.Z.........ZZ.......Z.....Z...Z.......Z...Z.....Z.
.......ZZ...Z..ZZ......Z......Z..Z...ZZ....ZZ.............Z.................Z....Z...Z.Z.
...............................Z..Z.......Z.ZZ.Z...................Z....Z.........Z.ZZ...
Z............ZZ..Z........Z.Z........ZZ......Z.Z...........Z..Z.......Z.........Z..Z.Z...
.....Z.Z.ZZZ.....Z.Z.......Z..Z..Z.Z.....Z.Z............Z...Z.......Z......Z.............
Z...Z....Z...............Z..Z....Z....Z......ZZ.....Z.......Z...Z....Z........ZZ..Z....Z.
ZZ....ZZ.Z.ZZ.Z...............Z..ZZZ..........................Z...Z...Z..........Z..Z....
Z............Z..........ZZZ.Z........Z..Z.............ZZ..............Z..........Z.......
.ZZ.........................ZZ.ZZ......Z..Z.ZZ.......Z...Z....Z........Z.....Z...Z.......
......Z....Z......Z..Z...ZZ.....Z..ZZ..Z.......Z..Z.......Z.....................Z.....Z.Z
....Z.Z..........Z.Z..............Z..........Z.........Z..........Z..Z.............Z.....
....Z.......Z...Z....Z.Z.Z.Z...........Z.Z.Z....Z.ZZZ...................ZZ......Z.Z......
..........Z....Z................ZZ..Z...ZZ..............Z..Z...Z.Z..........Z............
..........Z..Z......Z...Z....ZZ....Z......Z...Z....Z.Z...........Z..........Z..........Z.
.Z.............Z.ZZ.....Z..ZZ..Z.........Z........ZZ....Z......Z......ZZZ................
................Z.Z.Z.Z........ZZ.....ZZ......Z.........Z...Z.Z.Z......Z.Z...............
.......Z......................Z..............ZZ....Z...Z.Z..Z......Z......Z..........Z.Z.
...Z.....Z..Z...Z..Z..Z.Z.......Z.....Z..............Z.Z.........Z.....Z..Z.Z.Z.Z.Z.....Z
...Z.........Z...Z.................Z.....Z..........Z..........Z........Z...Z....Z..Z..Z.
........Z.Z.Z.....Z..............Z.....Z......Z.....Z.Z..Z....Z....Z..Z.......ZZ.Z..Z....
.Z......Z......Z.Z.....Z................Z.....Z.........Z..Z........................Z....
.......Z....Z......Z...Z.....Z...ZZ........Z...............Z.Z.......Z.......Z.......Z...
....Z...Z...........Z................Z..................Z.Z...Z..ZZZZ............Z.......
.........Z............Z.....Z....Z.ZZ............Z...Z....Z...Z.ZZZ...Z.ZZ.Z..Z......Z...
.ZZ............Z..Z.......Z........Z..Z..Z...Z..Z........Z..Z........Z.........Z.........
Z.....Z....Z.Z.ZZZZ.....ZZ...ZZ......Z.....Z......Z..Z.....Z........Z.............Z...Z..
Z......Z...Z..Z.....Z....Z.Z...ZZ.........Z..ZZ....Z..ZZ........Z..........Z....Z........
..Z.Z.....Z.............ZZ.....ZZZ.....ZZ..Z......Z..ZZZ..Z..Z..Z.ZZ.....Z....Z....Z.....
.....Z.....Z.Z.....ZZ.............Z..Z...Z....Z.ZZ....Z...Z....Z..Z......Z............Z..
.........Z...ZZ........ZZ...ZZ...........Z.....ZZZZ.ZZ....ZZ...Z............Z.........Z..
...Z....Z..Z......Z......Z.......Z...Z.Z.ZZ..Z.Z......Z...Z...Z.Z...Z.Z..........Z...Z...
............Z.ZZ......Z......Z.....Z......Z.........Z....ZZ..Z..Z..........Z......Z.....Z
..Z..Z..Z.....Z..ZZ............Z.Z..........Z.....Z....Z....Z..ZZ...........Z.....Z....Z.
....Z.........Z....Z.........Z.........ZZ..Z..Z.............Z.ZZ...........Z..........Z..
.......Z...Z.Z...........Z.......Z........Z...Z.....Z..Z.......Z....Z.Z......Z...........
.ZZ....Z...................ZZ.........ZZ....ZZ....Z..........Z..ZZ...Z.Z.................
..........Z...........Z........Z.......Z.Z.....Z..Z.....ZZ.Z..Z........Z...Z.....Z.......
......Z.......ZZ..........Z......Z...........Z.Z...Z.........ZZ..Z................Z..Z...
.Z.............ZZ......Z..............Z..........................ZZZ........Z..Z..Z..Z...
................Z.....ZZZ.Z...Z..Z..Z............................Z..Z.Z...ZZZZ...........
.................Z......Z.........Z...Z...........Z........Z..Z.....................Z....
...............ZZ..Z.......ZZ.......Z.....Z...........Z.Z.......Z.......Z..Z........Z..Z.
.......................Z............Z.......Z.Z.....ZZZ..Z..........Z..Z....Z..Z...Z...Z.
......Z..................Z...............Z..Z....Z.Z..Z..Z.................Z......Z...Z..
...Z.........ZZ...ZZ...........................Z........Z....Z....Z..........ZZ..Z.Z....Z
.....Z......Z....Z.......Z..Z......ZZ.Z.Z....Z...........Z.Z....Z...Z.......ZZ.Z......Z..
.........Z..........Z...Z................Z.Z........Z.Z..........Z.....................Z.
..ZZ.............Z...ZZ.Z...........Z..........ZZ....Z.....ZZZZ...........Z.Z.........Z..
.ZZ.ZZ.Z.............Z......Z............Z....Z...............Z....Z....Z.............Z..
...Z........Z..ZZ.....Z..........Z......Z......................Z..........Z.Z.Z....ZZ....
......Z...Z.Z.ZZ..........Z.........Z..ZZ.......Z..Z......Z.....Z...........ZZ...........
Z.Z..Z.......Z.Z.....ZZ....ZZ......Z....Z.....................Z........ZZZZ...........Z..
...Z...Z.ZZ.....Z.Z...Z..ZZ.......Z.......Z...........Z.........Z.......Z...Z...Z......Z.
Z.....Z.Z..Z.Z.............ZZ.........Z....ZZ.........Z...............Z..............Z...
.................Z.ZZ...Z..Z............Z.Z.Z.......Z..ZZ..........Z.......Z.....Z..Z.Z..
...........Z.Z....................Z......Z......Z.Z..ZZ.......Z.....Z......Z.............
....Z.Z......Z.....ZZ...............ZZ.....Z......Z.Z..Z..Z.....Z..Z........Z....Z.......
.....Z.........Z......ZZ.......Z.Z........Z..Z.......Z.Z...Z.Z.Z....Z.ZZ.ZZZ.............
.Z.....Z...Z.....ZZ........ZZZ...Z.ZZ..ZZ.Z.ZZ.................Z.......Z....Z..Z..Z...Z.Z
..Z.....Z......Z........Z..ZZZ...Z...Z........Z.Z....ZZ..Z...Z...Z......Z.Z..............
.......Z..........................Z.Z....ZZ..Z........Z..................................
....Z..Z.Z.Z.......Z..........Z..Z.....ZZ.........Z..Z.........Z.Z.Z.....Z...............
........Z...Z.Z.......ZZ.Z........Z....Z..............Z.Z...Z.....Z.....Z................
.........Z..Z.........Z..Z...........Z...ZZ.........Z.......Z.....Z..Z..............Z....
74 78
.....Z.............................Z.....Z..........Z.Z............Z......
...Z...ZZ......Z.ZZ......Z......Z...........Z.....................ZZ......
.......ZZ..Z....Z...Z...........Z.......Z.......Z....Z..Z.................
...ZZ....Z......Z....Z....Z........Z..............Z..........Z..........Z.
Z.Z...Z...Z.Z....Z.........ZZ.....Z..........ZZ...........Z...Z...........
.ZZ......Z...........Z.......ZZZ.ZZ....Z....ZZ..Z...Z...............Z..ZZZ
......Z.....Z.....Z..........Z.......Z......ZZ....Z.ZZ...........ZZ.......
.Z......Z................ZZ.....Z........Z..........Z...Z.....Z...........
.....Z..Z..Z.ZZ.Z....Z....Z..ZZ..Z.....Z....Z.Z........ZZ..........Z......
..........Z......Z......Z...ZZ..Z....Z...Z.Z.....Z....Z.ZZ.Z..............
....Z............Z.Z...........Z...Z...........ZZ......ZZ...Z.Z.Z..ZZ.Z..Z
.......Z....ZZ...Z.Z........Z..Z...ZZ........................Z...Z....Z...
...........Z....Z.....Z.........Z.Z.........Z.....Z..........Z......ZZ..ZZ
....Z....Z...Z.........ZZ.Z.....ZZ.........Z.......Z..Z............Z......
..ZZ.ZZZ........Z.......Z.......Z........Z...Z.Z....Z........Z......Z..ZZ.
.............Z....ZZ.......Z....ZZ...........Z.Z.....ZZ.................Z.
...........Z.......ZZ...Z.........Z..................Z......Z...Z..Z..Z...
.......Z........Z...........Z.......Z.Z........Z..........Z...............
Z.....Z....Z.....Z.Z..Z......Z...........Z..........Z....Z..Z.Z......Z....
.Z.......Z..Z...Z.Z......Z.....ZZ.....Z....Z..............Z...........ZZ..
.....Z....Z.Z..Z..Z.........Z...Z.Z..Z........ZZ.....Z........ZZ.ZZ....Z..
....Z.................Z.........................Z........Z............Z...
ZZ....................ZZZZ....Z.Z..Z..Z....................Z.Z..Z.Z.......
....Z...ZZZ..........Z.....Z.......Z....ZZZ.............Z..........Z......
.........Z.........Z...Z..Z....Z.....Z....Z...Z..ZZZ..Z...................
Z............Z...Z.ZZ.Z...Z...Z.....Z....ZZ..Z..........Z....ZZ...........
.ZZ.........Z....Z.Z.....ZZ....Z.....Z......Z........Z..Z.....Z.......Z...
............Z....Z..............Z.Z......Z.....Z.ZZ...............Z......Z
.Z......Z....Z....Z...ZZZ...............Z....Z....Z....Z.......Z.Z.......Z
..........Z.......Z...Z......Z..Z...Z.................Z.....ZZ..Z.......Z.
...Z......Z........Z........Z.Z..Z.Z.Z.....................Z.Z..ZZZZ..Z...
...................Z......Z.................Z......Z.Z...................Z
.......Z........Z......Z.....ZZ.......Z....Z.Z.............Z.Z.......Z....
Z......Z..Z......ZZ....Z..Z..........Z...................ZZ....Z.Z...ZZ.Z.
.Z.Z......Z...Z........Z.................Z.........Z...Z....Z.Z..Z........
.......Z...Z....Z.Z.ZZZ..ZZ.ZZ...Z..........Z.Z....Z..Z.Z...........ZZ..ZZ
...........Z.....ZZ.Z....Z.Z.Z.......Z.Z......................Z.ZZ...Z....
.ZZ.Z........Z.ZZ.Z.....Z...Z.....................Z..Z...........Z........
Z............Z.........Z..Z...Z.Z.ZZ......................................
...Z..................Z....Z.......ZZ....Z.Z............Z....Z.......Z....
........................Z.....Z...Z......Z....Z...Z............Z.........Z
...Z.Z.Z....Z......Z.Z......Z.Z...........Z.Z....Z......Z..Z..ZZ...Z..Z..Z
....Z....................Z......Z......Z....Z.....Z....Z..ZZZ...Z.........
.....Z..Z..Z....Z.ZZ...................Z.......Z......Z..Z.......Z........
..Z.Z.Z.Z.....Z.................Z.....Z..Z........Z.....Z.....Z........Z..
..ZZ.................Z.....Z..Z.....Z.Z......Z.Z..Z...................Z...
....Z...........Z....Z.Z..........Z...Z..Z...ZZ...Z..Z..Z..........Z.....Z
..................Z...Z..Z.Z.Z.Z....Z.......ZZ.......Z..Z...........Z....Z
.Z....Z..Z......Z.............Z......Z.....Z....................Z..Z.Z...Z
Z......Z....................................ZZZ...ZZZ.................Z...
Z..Z...........Z...Z........Z...Z...ZZ...Z.........Z.Z.Z.Z.ZZ..Z....Z..Z.Z
........Z...Z...ZZZ........Z......Z....Z.......Z.....Z....Z...Z..Z........
.Z.....Z.Z....Z.............Z.....Z.Z.....Z...Z.Z.....Z....ZZ...Z.........
........Z..Z.Z...Z..........Z...Z.....Z.....Z.....Z.................Z.....
...Z..Z........Z.....Z..Z...Z..........Z.........Z.Z...Z.....Z...Z....Z...
Z...Z.......Z..Z..............Z....................Z.....Z.............Z..
.Z...............Z..Z...............ZZ...........ZZ........Z...ZZ.Z.Z..Z..
.Z..Z..Z......Z...Z..........Z...ZZ..................Z........Z...Z..Z....
......Z..............ZZ..Z.Z..ZZZ..Z...Z......................Z.......Z...
............Z.............Z..Z.....Z.....ZZZ.....Z.Z...ZZ..Z......Z.......
Z.Z..Z......ZZ.Z.....Z.Z...............ZZ..Z.Z.......ZZ...................
..Z.......ZZ.Z.Z.Z.....Z......Z.Z..Z......ZZ......Z..............Z....Z...
.............Z..........Z....Z..............Z............Z........Z..Z.Z..
Z.....Z.Z...ZZ..Z.........ZZ....Z..........Z.................ZZ....ZZZ....
..ZZ..Z...ZZZZ..Z......Z.......Z.Z.Z....Z.........Z....Z.....ZZ.........Z.
...Z....Z.ZZ.Z............ZZ..ZB.Z....Z.............Z.........Z...........
........Z..Z.Z.Z...Z.......Z.Z..Z..............Z..Z.Z....ZZ.....Z..Z......
......Z....ZZ.....Z........Z.....ZZZ..Z...ZZZ........Z.Z.Z.Z..ZZ.ZZ.ZZ...Z
....Z.ZZ..Z.....................Z...................Z.......Z.....Z......Z
.Z.Z.Z....Z..Z.....Z....Z.......ZZ...Z.......Z.....ZZ.....Z...Z.Z..ZZZZ..Z
...................Z.Z....Z..Z.......ZZ..Z..Z.Z.....Z..Z..Z..Z.....Z...Z..
...Z.....Z.Z.....Z..............Z...ZZ...Z......Z...Z.Z...Z..............Z
ZZ......Z.................Z......Z...Z.Z.Z..Z...Z.........Z..Z.....Z......
Z....Z.......Z...Z.....Z....Z...A...Z..Z.Z...Z...Z...Z...Z....Z.Z..Z...Z..
...........Z..ZZ....Z............Z......Z.Z.........Z.......Z..Z..........
.ZZ......Z..........Z......Z..Z............Z...Z....Z.Z..Z......Z...Z.ZZ..
.........Z.Z...ZZ.........Z.ZZ..Z....Z....ZZZZ....................Z..Z.Z.Z
......................Z..Z..............Z.....Z.Z.Z...Z...Z.....Z...Z...ZZ
83 54
.Z....Z.....ZZ..Z....Z.............Z.............Z...Z...ZZ.....Z.........Z...Z....
Z.........Z.....Z.......................................Z....Z.Z...........Z.Z.....
Z......Z.......Z......................Z...................Z...ZZ............ZZ...Z.
.....Z....Z..Z.................Z..........Z..........Z.Z.Z..........Z.....Z.....Z..
..ZZ.......Z........ZZZZ...Z.......Z.......ZZ............ZZ...Z..Z.Z...........Z...
..............ZZ..Z.Z........Z.....Z.Z.........Z...Z...Z....Z....Z.................
.....Z...................ZZ........................Z........................Z......
.................Z..Z...............Z...................................Z.Z........
.......Z.Z......Z.Z...........Z....Z..........Z......Z.............Z..ZZ..........Z
.....Z...........Z............ZZ.Z..................Z..Z.......Z...........ZZ....Z.
.......Z......Z...Z...Z.........Z...Z.......Z.Z......ZZZ.....Z...Z..Z............Z.
Z..Z.....Z....ZZ....Z.Z....Z.....Z......Z.Z..Z...................Z.Z.......Z..Z...Z
.................Z.....Z......Z....Z......Z........Z..Z.....Z....................Z.
..ZZ..Z..Z...............Z....Z....Z.......Z..........Z.Z.Z......Z.Z...............
Z.Z.....ZZ....Z.........ZZ.....Z..Z........Z...Z.....ZZZ..........Z.Z.............Z
.................Z........Z..Z...Z..Z.........Z...Z..........Z.....Z..ZZZ.....Z....
....Z..........Z.Z.................Z.....ZZ....Z.Z.......Z..ZZ.....................
....ZZ.........Z.................ZZZ.........Z.....Z...Z...Z......Z...Z..Z....Z.Z..
...Z.................Z.....Z.ZZ..........Z..............Z.......ZZ.Z.....Z...Z...Z.
.Z........Z........Z..Z.....Z.....Z...........................Z....Z.Z.......Z.....
..Z......Z.............Z.....Z..Z..Z.......Z.Z..Z.Z......Z................Z...Z..B.
.......ZZ.....ZZZ............Z............Z.......Z.Z.....Z...Z..Z.................
ZZ.....ZZZ..Z..Z......Z....Z...Z.......ZZ.Z........Z.Z.....ZZ..Z.......Z....Z......
.....Z....Z....Z.................Z...Z..Z.....Z.....ZZ.ZZ.Z..Z....Z.......Z...ZZ.Z.
ZZ.Z.Z.Z................Z.......ZZ.Z..............Z..Z...Z.....Z......Z......ZZ...Z
......Z...Z.........ZZ..............Z..............Z.......Z..Z........Z...Z...Z...
.Z.......Z.........Z.............Z...ZZ.Z.........Z....ZZ........Z........Z...ZZ..Z
.............Z............Z..Z.....Z....ZZZ.......Z..Z.Z..........Z....Z.......Z...
.....Z....Z..Z....Z........Z.....Z.Z..........Z..Z.Z..Z........Z..........Z.Z.Z...Z
Z..Z..Z..Z........Z.................Z...............Z............Z...Z...Z.Z.......
.Z..Z..ZZ.....ZZZZ.......Z...Z.Z....Z.......Z..Z.........ZZ...Z...Z.......Z........
Z.Z.Z..Z.....Z...........Z....Z...........Z........................Z.Z.....Z.......
..........Z.....Z...Z.Z..Z....Z...Z..........Z........Z.......Z.Z....Z.....ZZ......
..........Z....Z...Z.....Z...Z..Z..............ZA......Z.........Z....Z...Z.......Z
.........Z.Z........Z.............Z..Z....Z.Z.....Z...........Z....Z...Z...........
........Z...ZZ....Z.......Z....ZZ..........Z.Z......Z...............Z..Z...........
.......Z...ZZ.Z............Z......Z..ZZ.ZZZ.ZZ.....Z....Z..Z......Z.ZZ.Z..Z........
......Z..Z.....Z..Z....Z..........Z...Z......Z.......Z.........Z......Z..Z......Z.Z
.Z.....Z..............Z.Z.....Z............Z...........Z...Z..Z.ZZZZZ..............
................Z..Z.Z.....Z........Z................Z.............Z.Z......Z......
.....Z.Z.......Z....................Z...Z......Z.................Z..Z....Z......Z..
.Z......Z...Z....Z......Z.....Z..Z......ZZ........Z........Z........ZZ...Z.....Z..Z
...Z....Z......Z....Z........Z...........Z.....Z..Z.....Z...............Z.....Z....
.......Z..Z...Z..ZZ..........Z...........Z.........ZZ......Z...Z..Z.Z...Z.......Z..
Z.ZZ.....Z.Z...................Z.......................Z.Z.....Z...........Z...Z...
..............Z..Z.....Z........Z....Z..Z.................Z........Z...Z.......Z..Z
.Z.......Z......Z..Z.........................Z.................Z...Z.......Z.......
ZZ.Z........Z...Z..Z...Z.Z.....Z.ZZZ..Z........Z.Z..Z.....Z........Z....Z...Z......
.....................Z....................Z.......Z...ZZ......Z........Z.Z.........
Z...........ZZZ................................Z...............................Z..Z
........ZZ..Z.Z...Z.Z........Z..Z..................Z.....Z.....Z...Z.............Z.
.....Z........Z..........Z...Z.Z..Z...ZZ....Z.............Z.......Z..Z...Z.........
....Z........Z..ZZ.......................Z....Z..Z.........Z..Z.Z......Z.Z.........
.....Z.....Z.......ZZZ.Z.Z.ZZ.......Z.........Z..Z.....Z.........................Z.
82 90
........Z.Z....ZZ......................Z.Z..............ZZ...Z....Z......Z.Z.....Z
...Z..Z...........ZZ.Z...Z.Z.ZZ.....Z....Z.Z..Z...............Z..............Z..Z.
....ZZ...Z.Z.....Z......Z....Z.Z.....Z.......Z...Z............Z......Z.Z........Z.
.Z.Z..Z....Z....Z...Z....Z....A.Z...Z.Z...............Z..Z.........Z.ZZZ..........
.....ZZZ...............ZZ...ZZ.....................Z.......Z......Z..........Z....
....ZZZ......Z...Z.ZZ......ZZ.Z.............Z..Z....ZZ.........Z......ZZ....ZZ...Z
............Z....Z......Z.Z.Z.......ZZZ.....Z..........ZZZ........................
.Z.....ZZZZ....Z.................Z............Z...Z...ZZ.Z..Z....Z....Z..Z.Z......
.Z...Z.Z........Z..Z....Z.....ZZ.Z......Z..Z...ZZ...Z...............Z.............
..........Z.Z....Z......Z...........Z..Z.....Z.Z.Z..Z..Z............Z...Z..Z.Z....
...Z............Z...Z............ZZ...........Z.....Z.Z.Z..Z.......Z.......Z....Z.
...Z.......ZZ...Z..ZZ..Z...Z..................Z....Z......Z..........Z..Z...Z.....
.........ZZ..Z.Z...Z......Z.Z...Z.Z.Z.Z.....Z........Z......Z.....................
.....Z..ZZZ.....ZZ.......Z............Z......Z......Z.......ZZ.Z...Z.Z..ZZ..Z.....
..............Z......Z...Z..ZZ.Z....Z..................Z......Z....Z.....Z......Z.
Z...Z.Z.ZZ............Z...Z.Z....Z..........Z.Z.......Z.....ZZ...Z....Z..........Z
.Z.....Z.Z.......Z..Z.Z.....Z........ZZ........Z.Z.Z....Z.Z.Z.Z.Z......ZZZ....Z...
.Z................Z..ZZZ...........Z.Z....Z...Z.................Z.................
.ZZ..ZZ........Z....Z...Z...........Z.........................ZZ..Z..ZZ.........Z.
Z.......Z..............................ZZZ......Z.ZZ........Z...Z.......Z.........
.........Z........ZZ...Z....Z....Z..................Z.Z..........Z.Z...Z..........
Z.....Z.ZZZ..Z.Z..Z.....Z......................Z....ZZ..................ZZ......Z.
Z........Z...Z.Z..............Z....Z..........Z.....Z.Z..Z.....Z...........ZZ.....
...Z....ZZ..Z.Z.Z..Z....Z..Z..........Z.ZZ.......Z.........Z..........Z.....Z..ZZ.
...Z........Z..........Z...Z....Z...............Z..Z..Z..Z...Z.......Z......Z..B..
.Z..Z.....Z...Z...........Z..........ZZ..................................Z......Z.
.Z......ZZ.......Z......Z...................Z...Z....................Z....ZZ.....Z
.....Z....Z...Z......Z.ZZZ.Z......Z....Z........Z.Z...Z.....Z.....Z..ZZ.Z.Z.......
.........Z.Z........Z...Z.......Z.Z...............................Z..Z..Z....ZZZ..
...Z...Z.......Z.....Z..................ZZ..Z...........Z.Z........ZZ.Z......Z....
............Z.Z..........Z.ZZ.......Z.................Z...........Z..Z.....Z......
Z..Z......Z.....Z.ZZ...........Z...Z.....Z...Z...........Z..Z....Z..Z...Z.........
..Z...ZZ..Z..............Z...Z..........Z..Z........Z..........Z...Z......Z.Z.Z...
....Z.....................Z...Z.Z......Z...Z...Z................Z.Z.Z......Z......
..Z........Z............Z.......Z......Z.........Z.Z.......Z....Z........Z...Z....
Z.Z..Z.Z...Z...Z...Z...ZZ....Z...........Z....Z...........ZZ.........ZZ....Z.Z..Z.
.....Z.Z........Z.Z....Z.....Z............Z...Z...Z..Z...Z.Z.....Z..Z..Z...ZZ.....
........Z.Z.........Z.Z.....ZZZ.Z....Z......Z..Z...Z.....Z..Z............Z........
.........Z.....Z..ZZ..Z...ZZ.......Z...Z.....Z....Z..Z....Z...................ZZ.Z
.......................ZZ....Z.Z..Z......Z..Z..........Z....Z...ZZ.Z..Z...Z.......
ZZ.....Z.Z.....Z............Z....Z..Z.ZZ........ZZ..Z.Z.ZZ....ZZ....ZZ............
.Z.Z.......Z.....Z........Z.Z.ZZ.................Z....ZZ...Z...ZZ........ZZ.......
...Z.Z...Z..Z......Z..Z...Z....Z.Z.....Z.Z...Z.ZZ......Z......................ZZ..
....Z...Z............Z...ZZ.Z.ZZ.........Z....Z.............Z.......Z.............
.Z......Z...........Z.......Z...........Z...............Z.......Z..........ZZ.Z.ZZ
.....ZZ...........Z..Z.Z...Z..ZZ.Z.Z..Z..........ZZ.......Z......ZZZ..Z..Z..Z.Z...
.....ZZ...Z.......Z....Z..Z..Z......Z.Z..............ZZ.Z..................ZZ.....
ZZ.....Z...Z...........Z...........Z.Z....Z...Z............Z......ZZ......Z.......
..ZZ.....Z............Z..Z..Z.....ZZ.....Z......ZZ........Z..ZZ..Z....ZZZZ...Z....
ZZ........Z..Z.ZZ.Z.....ZZ.Z.Z.Z...ZZZ.........Z.......Z......ZZ...Z.Z...Z......Z.
..............Z.Z.Z.........Z.....Z...........Z.....Z.Z........Z..................
.Z.ZZZ......................Z.Z...................Z...Z...............ZZ.Z........
........Z.............Z..........Z.....Z....Z....................Z......Z.Z.......
........Z..Z.Z..........Z..Z.....Z......Z.........ZZ....Z.Z......Z........ZZ......
.ZZ....Z...Z.Z..Z.....ZZ........Z..Z.....ZZ....Z.........ZZ..Z.ZZ...Z....Z.Z.Z....
Z...............Z...........Z..Z...Z.....ZZ.Z................Z.....Z.........Z....
..ZZ...ZZ........Z....Z...Z..Z..........ZZ.............Z.............Z.Z..Z.......
.......................ZZ........Z.....Z.....Z........................ZZ..........
......Z..Z....ZZ.................Z...........Z.Z................Z......Z..ZZ..Z...
.....Z........ZZ.....................ZZ..ZZ....Z.....ZZZ.Z.......Z....Z...........
....Z....Z...........Z....Z......Z..ZZ.ZZZZ........Z....Z...........Z.............
.......Z.........Z...Z.......Z...Z............................Z..Z.......Z........
......Z...................Z.Z.....Z....Z.........ZZZ...Z.......Z.ZZ...Z.........Z.
.Z......Z.........Z.Z.........Z.ZZ..ZZZ....Z.Z.......Z.............Z....ZZ.Z......
.Z.Z...........Z....Z............Z...........Z...................Z.........Z.Z....
........Z.Z..Z.Z.....Z.Z.....Z....Z.Z...Z......Z...Z.....Z....ZZZ.........Z..ZZ...
.Z......ZZ.....ZZ.......Z....Z...................ZZ..........Z...Z......Z..Z......
....Z........................................Z........ZZ..Z....Z........ZZ.......Z
....ZZ.ZZZ....Z....ZZZ....Z..ZZ..Z............Z.......Z......Z.Z.Z....Z.....Z..Z..
......................ZZ.....Z.....Z......ZZ.Z..Z......ZZ...........Z.Z.....Z....Z
..Z..ZZ....Z.Z.....ZZ......Z...Z.......ZZ.Z......Z.....Z...Z..ZZ..ZZ......Z.......
....Z..Z...Z.....Z..ZZ.Z.....Z....Z..Z........Z......Z............................
....Z..Z...Z........Z..Z.......ZZ.......Z...........Z.....Z.Z.....................
...Z......Z.....Z......Z......Z..Z.Z.......Z.ZZ.Z........Z..Z.......Z...Z..Z.Z....
.Z............ZZ..Z.Z......Z....Z...Z......Z....Z......Z....Z.................Z.Z.
...Z....Z....ZZ.......Z.Z...Z...ZZZ.Z..........Z....Z...Z.......Z....Z...Z........
...............Z......Z..Z..Z.....Z......Z....Z.........Z......Z....Z..Z..........
...ZZ......Z...Z.........Z.Z...........Z.....................ZZ......Z...........Z
.....Z.........Z........Z........Z...Z.......Z.........ZZ.Z...................Z.Z.
..Z...ZZ..........Z.................ZZ.Z.............ZZ.................Z......Z..
ZZZ.........Z.........Z...........ZZ......Z......Z...........Z...ZZ.Z.......Z.....
.Z.Z........Z...............Z........Z..ZZ....Z..ZZ......Z......Z......ZZZ........
.........ZZ..Z.......ZZ....Z.......ZZ........Z....Z.........Z.Z...................
..........Z.Z..ZZ..ZZ....Z.Z....Z...Z....Z..........Z..ZZZZ.Z...Z.Z.Z...ZZ.Z.Z...Z
.....Z.Z....Z..Z.Z..Z..Z....Z..Z.Z...Z....Z.......ZZZ.Z.....Z..Z..Z.....Z..Z....Z.
.......Z..Z..Z.ZZ..Z.Z...Z.Z.....Z...Z....Z.....Z........Z...Z.......Z.....Z.....Z
.......Z...........Z...Z.........ZZ.Z.Z.Z......Z...........Z..Z....Z..........Z...
..Z.....ZZ..........Z...........Z......................ZZ.Z.........Z...........Z.
........Z..Z........ZZZ.Z.Z.......Z.........Z.Z.................Z......Z.Z.ZZ...Z.
..ZZ...ZZ.ZZ.........Z.......................Z......Z.......Z.Z........Z.ZZ.....ZZ
#include <iostream>
#include <time.h>
using namespace std;
int oo = 2000000000;
int T, n, m, result;
int xx1, yy1, xx2, yy2;
char mp[101][101];
bool vs[101][101];
int dx[8] = {0, 0, -1, 1, 1, 1, -1, -1};
int dy[8] = {-1, 1, 0, 0, -1, 1, -1, 1};
int kdx[8] = {2, 2, 1, 1, -1, -1, -2, -2};
int kdy[8] = {-1, 1, -2, 2, -2, 2, -1, 1};
int arr[80001][3];
int head, tail;
void init(){ head = 0, tail = 0; }
void push(int x, int y, int cnt){
arr[tail][0] = x, arr[tail][1] = y, arr[tail++][2] = cnt;
}
void pop(){ head++; }
bool isEmpty(){ return head == tail; }
int getX(){ return arr[head][0]; }
int getY(){ return arr[head][1]; }
int getC(){ return arr[head][2]; }
bool inSide(int x, int y){
if(x >= 0 && x < n && y >= 0 && y < m) return true;
return false;
}
// 0:left, 1:right, 2:down, 3:up
void bfs(){
init();
push(xx1, yy1, 0);
vs[xx1][yy1] = true;
while(!isEmpty()){
int x = getX();
int y = getY();
int c = getC();
pop();
if(x == xx2 && y == yy2){
if(result > c) result = c;
return;
}
for(int dir = 0; dir < 8; dir++){
int xx = x + dx[dir];
int yy = y + dy[dir];
if(inSide(xx, yy) && !vs[xx][yy]){
vs[xx][yy] = true;
push(xx, yy, c+1);
}
}
}
}
int main(){
freopen("input.txt", "r", stdin);
// Calc clock
clock_t time_start, time_end;
time_start = clock();
cin >> T;
for(int tc = 1; tc <= T; tc++){
// Initial && Input
result = oo;
cin >> m >> n;
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
vs[i][j] = false;
cin >> mp[i][j];
if(mp[i][j] == 'A'){
xx1 = i, yy1 = j;
} else if(mp[i][j] == 'B'){
xx2 = i, yy2 = j;
}
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(mp[i][j] == 'Z'){
vs[i][j] = true;
for(int dir = 0; dir < 8; dir++){
int xx = i + kdx[dir];
int yy = j + kdy[dir];
if(inSide(xx, yy)){
vs[xx][yy] = true;
}
}
}
}
}
vs[xx1][yy1] = false;
vs[xx2][yy2] = false;
// Solve Problem & Output
bfs();
if(vs[xx2][yy2]) cout << result << endl;
else cout << -1 << endl;
}
// Calc Time
time_end = clock();
cout.setf(ios::fixed);
cout.precision(9);
cout << "Time: " << double (time_end - time_start) / double (CLOCKS_PER_SEC) << " s." << endl;
return 0;
}Leave a Comment