Crazy King
quoc14
c_cpp
16 days ago
56 kB
2
Indexable
Never
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