首页 > 代码库 > C语言 解决迷宫问题练习
C语言 解决迷宫问题练习
利用C语言来解决类似迷宫的问题，下面例子分别用两种方法来解决！
[Problem]
There is a maze as shown in the diagram below. In the maze in the form of a 100*100 matrix, the white background represents the road while the yellow background represents the wall.
Assuming the upper left corner block to be (0, 0), the horizontal direction to be x direction and vertical direction to be y direction, the starting point of the maze is (1. 1) and the arriving point is (13, 13).
Create a program to determine if there is a path to reach the arriving point from the starting point.
In the following example, there is the path.
In the following example, the starting point is (1, 1) and the arriving point is (11, 11). Thus, there is no route.
It should be noted that the above example uses 16x16 instead of 100x100 because of the space limitation.
[Input]
The first line of the input file provides the test case number. The test cases are followed in next lines.
Total of 10 test cases are given.
In each test case, 1 refers to the wall, 0 refers to the road, 2 refers to the starting point and 3 refers to the arriving point.
[Output]
The output file outputs the test case number following the ‘#’ symbol. It is followed by a space, 0 or 1 to indicate whether the arriving point can be reached (1 - yes, 0 – no).
[Input Example]
1 111111111111111111111111111111111111111111111111111111111111111111111111111111... 121000000010000000000000000000000000000000100010001000000000000010000010000000... 101011111011101110111111111111111111111110101011101011111110111010111010101110... 100010001010001000100000000010000000000010001010001000101000101010001010101000... 111110101010111111101111111011101110111111111010111110101011101010101110101111... 100000101010001000001000001000101010000010000010100010101000100010100000100010... ... 2 111111111111111111111111111111111111111111111111111111111111111111111111111111... 121000000010000000100010000000000010000010001000100000101000000000000010000000... 101110111011111010101010111111111011101010101010101110101011111011111010111110... 100010101000000010001010001000001000001010100010001010100000001000100010001000... 111010101111111111111010101011101111111010111111111010111011111110111111101011... 101000100000100000001010100010100000100010100000100010001010000000100000001010... 101111101110101011111010111110111110101110101110101011101010111110101111111010... ... |
[Output Example]
#1 1 #2 1 ... |
PS：maze2_test_input.txt
111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111210000000100000000000000000000000000000001000100010000000000000100000100000001000000010001000000011101011111011101110111111111111111111111110101011101011111110111010111010101110111110101010101111101110001000101000100010000000001000000000001000101000100010100010101000101010100000100010001000100010111111101010101111111011111110111011101111111110101111101010111010101011101011111010111111111110111011100000101010001000001000001000101010000010000010100010101000100010100000100010001000000000001000001110111110101110101111101110111010101111101011111010101010111010111011111111101011101111111110101111111010001010001010001000100000101010000010100000101010100010001000101000100010101000000000001010100011101010111110101110111011111110101011101011111010101011101011111011101010101010111111101111101011101110101000100010001000001000000010101000100010001000100000100010001000100010001000000010100000101000111010111010111011111011101111111010101111101011111111111111101011101111101111111111101110111110101111101000100010000000001000100000100010001000100000001000001000100000100000100000000010000010001010001110111011111111111111101110111011111110101111111110101110101111101111111110111111101111111011101110111000100010000000000000101000100000001010100000001010101000101000100000000010000010100000000010000011111011101011111111111110111011101111101010111011101010111110101110111111111011101011101111101111101110000010100010001000100010001010000000100010100000101000100000100010000010000010100010101000100010111011101010101010101010101011101111111111111011111110111010111110111010111011101111101010101010101011100010101010101000101010001000000000000000001000000000101010000010001000001010100000100010101010101110101010111010111110101111111111101111111110101111111010101011111111111011101010111110111010111010111010101000101010001010000000000010100010001000100000101010100000001000100010101010000010001000001011101011111010101011101111111111101110101010101111101110101011111110101011101010101110111011101111101110101000101010100010000000000010001010001010000000100010001000001000100010001010001010001000100010111010101010101011101110111011111110101111101110111110111110111011111111101011101110101010111110101011101010101000100000101000101000001000100010101010001000001000100000000010101000101010101010000010001110101010111111111010111010101110111110111010101010111110111011111111101011101010101110111011111011111010001000100010001000101010001010000010001010101000000010100000001000100000101010001000001000100011101111101110101011101110101110101011101011101010111111111011111110101011111110101110101111101011111110101000100010101000001010100010001010001000101010100000000000001010100000001000001010100000100000111010101010111010111110101110111111101111101110101010111111111010101011111110111110101110111111111011100010101010100000000010100010001000000010000010100000100000001010001000001000001010001000001010001111101011101011111111111010111010101011101011111011111110111111111110101110111111101110111110101011111010101000000000100000001000001010101000100000100000001000000000100010001000000010001000001000100011101010101111111110111111111111101110101111111011111110111111101010111110111111101110111110111011101110001000100010001000100000001000100010000000100010001000000010100000001010100000100010001000100010111011111110101010111010111011101110111111111011101010111111101111111111101010111110111110101111101011100010000010001000001000101000100010000000101000101000001000100000001000101000000000000010000010101111101011111111111110111010101111101011111110101111111010101110111110101110111111111111101111101010111000100010001000101000101010100000100000001010100000101010001000001010100000000000100010000010001011101111101010101010111010101010111111111110101011101010101110101111101010111111111110101111101111101110001010101010100000101010100010000000000010100010100010001000100010000010000010000010101000100010111110101010101011111110101011111110101111111011101011111110111110101111101011101011111010101111101011101000100010100010000010100000001010100000001000101000100000001010100010101010100010101000000000101110101111111011101011111011101110101110111111101110101011111111101010101110101010101010111011111110111000100000101000101000101010001000100010000010000010100010000000101010000010001010100000101000000011111110111010101110111010101110111010111110101110111011101011111110101111111011101011111011101111101110001010000010000000001010001000101000000010100010001010100010001010001000101010100000101000100010111010101111111011111011101010111010111111111010111011101011101011101110111010101011111010101110111011101000100000101000101000101000101010100000001000101000001000100010000010001010001000101000100010001110111110111011101010101110101010101010111111111110101111101110101111111011101011111010111111101011111010000010001000101010001010101010101000100000100010100000101010000000001000100000101000100000101011101011111010101110101110111010101010111010111010111010111010101111101110101111111010111011101110101110101010001010100010001000001010100010001010001010001000101010001010100010100000000000100010000010111010101011111010111111111110111011111011101011101011111010101110101011111011111111111011101011111011101010100000101000000000001010001000001000101000101000101010000000100000001000001000100010100010001110101011111010111111111010101011101111111010111010101010101111111111101111101110101011101011101010111010100000101000101000001010100000101000001000001000101010000000000010000000101010101000101010101011101011111010111010101111111011111110101011111111111110111111111111101111111110101010101110101010111110001000101010000010001000100000001000100010000010001000000010000000100010000010101000101010101000111011101010101011111110101011111110111111101011111010111111101011111110111011101010111110101010111011100000100010000010000010100000001000001000100000001000000010100010000010000010101010000010100010001111111110111111101010111011111110111110101110111111111011111010101111101011111010101011111010111010111010000010001000101010001000100010001000101000100010100010001010100010001000001010001000001000101011101011111010111110101011111010101011111110111010101011101011101010101011101111101110101111111010101110000010001000000010100000001010100000000000101010100010101000100010100010000000100010100000100010111011111011101111111111101111101011101110111110101010111010111011111011111110111110111010111011111011101000101000100000100000100000100010100010001010100010001000101000100000001000100010101000100010001111101010111110111010111110111111101010111010101011101011111011101011111110111011101010111110101011111000101000000010100010001010000000001000101010100010100000100010100000001000100010101000001010100011101110101111111011111110101011111111111110101010101111101111101011111110111011101010111110101011101110100010100000000000000010100010000000100010001010000010100000100000100000101000100010001010101000111010111011111011111111101011101011111010111111101110111010111110111011111010101111101010101011101111101000100010001000000000101000101000001010000000100010001010001000100000100010100000101000100010101110111011101011101111111110111110101111101111111110101011101010111011111011111011111010111111101010111010000010001000100000001010000010000000100010000010100000101000100010001000001000101000100010101011101111101111101110111110101011111111111110101011111111111110101110111011101111101010111010101010101110000010000010001010001010101000001000000010001000000000100010000010001010100000101000100010101010111011101111101110101110101010111011101111101011101111101011111011111011101010111110111111111010101011101000100010100010100010001000100000000010101000100010100000100000101000100010100010000000001000101111101110111010111010101110111011111111101011101111101011111011111110111011111010111011111111101110111000100010001000101010001000100000100010101000100000101000100000001000100000000010001000001000100011101111101011111110101011111011111010111010101110111110101011111110111010111111111110111010101110101110001000101000001010101000000000101010001010000010000010101000000010001000100000000010001010000010111110101110101110101011101111111110101011101111101011111110101111111011111011101111111011111111111011100010000010001000100010000010000010001010000010100000001010100000000010101000100000000010001000001110111011111010111110101110111011111110101110111011111110101011101111101010101110111110101010101111111010100010001010001010000010001000001000001000000000001010100010100000101010001010001010001010100011101011101111101010111111111011111010111111111111111111101011101110111110101110101010101111101010101110100000100010101000000000100000001000000000100000000000100000100010000010001010101010001000101010111010111110101010111111111011111111111111111010111111111110111110111010111110101010101111101010111011101000000010001010000000100000000010000000101010100000000010000010001000001010101010000000101010001110111110111110101011101111101111111011111010101010111111111110101110111011101010101111111110101010111000100010001010101010100010000000101000101010101000100000001010001010100010101010100000101010001011111011111010111010101010101111111010101010101010111010111110111110101011101010101010111010101111101110001000001010001000100010000000100010101010001000101000100000001010001000100010100010101000100000111011101111101011111111111011111011111110101111101010101011111110101111101111111011111010111010111111101000100010001000001000100010000010001010000010100010100010000010000010000000100000101000101000131110101111101111101110101011111011101010101111101011111111101011111111101010111111111010111011111010111000000000000000100000100000001000001000000010000000000000100000000000101000000000000000100000000011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112100000001000000010001000000000001000001000100010000010100000000000001000000000000010000010000000111011101110111110101010101111111110111010101010101011101010111110111110101111101111101110101111111011100010101000000010001010001000001000001010100010001010100000001000100010001000100010000010000000101111101010111111111111101010101110111111101011111111101011101111111011111110101111101111111111111010111010001000001000000010101000101000001000101000001000100010100000001000000010100010000000000000100011101111101110101011111010111110111110101110101110101011101010111110101111111010101111111011111111101110000000001010100010001000100000100010000010001010101010101010001010100000100010100000100000000010111111111110101111101011111011111010101111111110101010101011101110101010111011111010111010111111101011100000100010100010100000101000001010100010000010101000100010001000101000100000101010001000101000101110111010111010101011111010101110101110101110111010111011101010101110111111111010101011111010101110111000101010001010100010001010001010000010001000101010001000101010001010000000001000100000100010001011101010101110101010101011101010101111111110111010101011101111101111101010111111111111111011111110101110101010001000101010101000101010001000001000101000101000100000100000101010000000100000100000001000111010101110111110111010101111101110101110111010111111101110111110111110111011101110101011111110111111101010001000101000101010000000100010100000101000100000000010001000100010001010000010100000001000001110101110101010111010101111111110111011111010101010111111111010111010101011101111111010111111111110111010100010101000101010001000100010100010000010101000001000001000001010000000001000101010000000100011101010111110111010101110101010111011101111111010101111101111111111101111111110101010101011111010111110101010000010001010001000101000001010000000101000100010100010000010100000001010100010101000101000111110101110111011101010111110111110101111111011111110101010101110111010111110111011111110101010111011100010100010100000101010100010001000000010001000001010101010001000101010000010001000100010100010001110111010111010111110101010111010111011111011101110101010101110101010101110111011101010101111101010111010000010000010000010001010001010001000100000100010101010001010100010001010001000100010100010001011101111111011111111101110101011101011101011111110111010101110101111111110101110101111111010101111101110000010001000100010100010100010101000100000001000001010000010000000100010100010000010001010000010111011101110101010101010111011101011101111111110101111101111111111111010111010111111101011101111101011101010001010101010001000101000101000100010001010001010000000100000100010000010000000100010100010101110101110101010101111101110101110101110111010101110101111111010111011101111111011111111101010101011111010100010001010001010100010101000100000001010101000100010100000100000100010001000000010101010100011101010111111101110101010111010111110111111101010111010101011111111111110101011101011111010101111101110101000100010000010001000001000000000100010101000001010000000100010001010001010100000001000100000111010111010101011111111111111111011111110101010111011101111101110101010101111101011111111111010111011100000101010101000000000100000100000100010001000100010100000100010001000100000000000100000001010001111111010111010101111111010101011111010111111111011101010111110101111111110111111111110111110101111111000101000100010101000001010101000001010000000101000001010001010100010000000000010000010001010000011101010111010111010101011101010111110101011111010101111111010101110101111111111111011111010111111101110100010001000101010101000101010001010101000101010101000001010001010100000100000000010001000100010111111111011101110101011101110101010101010111010101010101111101110101010111010111111111011111010101011100000001010100010100000101010101010101010001000100010100010001000101000100000100000101000001010001110111111101010111011111110101010101110101011111110111010111110111110111011111110111010101111101111111010001000101010000000100010100010001010100000100010001010001000001000000000100010100010000010100011101010111010101011111010101011111110101011101110111011101010111110111111111010111011111111101010101110101000100010001010001010100000001000100010100000101000001000001000000010001000100000000010100010111010111010111111101011111011111110101111101010111110101111111110111111101111111011111011101011111011101010101010100000101000100010000010100000101010001010001000101000000010000000100000100010100010001110101010101010111010101011101010111110111110101010101110101010111111101111111011111011101011101010111010101010001000100010100010101010001000101000101000101000101000000010100000100000001000101000101011101010101111111011111011101010111010111010101110111110111110101011111010101111111111101111101110111110101010000010001000001010101000001000101000100010001000001010100000101010000000001000000010100000111010101111101011101110101010111111101010111010111011101011101111111010101111111010101111101011111011100010001000101010100010001000100000101000101000100000100010001000001000100010101010100010100000101110111110101110101010111011101010111111111011111011101111101110101110111110101010111011101011111010111010001010000010001010000000101000001000101000100010100010001000100010000010101010001000100000100011101010101111111111101011111110111110101010101011101010101110111110111011111010101011101011111011101110101010000010000000101000001000101000101010100000101010000010001010000000100010101000101010001000111010101011101110111110101110111010111110101011111111101111101010101011111011111010101110101011101111100010001010001010000010101010100010000010001000001000100010101000100000100000101010100000101000101111111111101110101111111010101011101011101111111010101110111010111110111110111010101011111010101110111010000000100010100000100010101000101010100000101010100000001010000010001010001010100000101000100011101011101010111010111011101010101110101011101010101011111110101011111010101010101010111011111111101110001000101000100000100000101010001010001000100010100000001010100010001010101010001000100000000000111111101110111011111011111110101011101011101111111011101110111011101011101010111111111011101111111011100000100010001000100010001010001000100000100000100010100010001010101000101000001000000010100000001110101111111011101011111010101011101111111110111111101110111011101010101111111010111111101011111111111010100000101000100010001000101010000000001000000000100010001000001010100000101000000010100000000011101110111010101111101011111110101111111110101111111110101011111011101010111010111111101111101111101110100010001000100010100010001000000000100010000010000010100000100010100010101000100010000010100010111010111011111110111011101011101111111110111111101011101111111011101011111010101010111111101110101011101000100000001000001000101000100000100010001010101010000000100010100010100010101010000010000010001110101111111010101111101110101110111010111010101010101111101111101011101010111010101010111111111110111010100000101000000000100000001010001010001010101000001000100000100010101000101010001000000000101011101010111011111111111111111011101011101011101010111111101010111111111010111011101011111110111010101110001010100010000000001000101000100010100010100010000010101000100000001000100000100000101000100010111111101011101011111110101011101111101010111010111011101011111010111111101011111111111010111011101011100010101000001000000000100000100000001010001000101000100000100010000000100000100000101000101000101110101010101111111110111111111110111111101011111010101110101111111011101111111010111010101110111010111010001000100000001010001000000000100010101000100010101010000000100010100000101010001010001000101011101110111110111110111010101111111110101010101111111010101111101110111010111010111010101110111010101110001010000010100010001010001010001010001010001000001000001000100010001010001010001010000010101010111010111011111010111011101110101010101111101010101111101111101010111011101011101011101111101010111011101000001000001010001010100000101000101000101000100000001000101000101000101000101000100010101000101110111111111011101011101011111110111110101110111110111111101011111010111010101110101110101010111010111010000010001000100010100000001000001010001010000010000010101000001010001010000010100010001010001011101110101011101111101011111110111110101110101111111011101010101111101011111111111010111111101011101110100010001000100000100010100000001010001010000000101000001010100010100000000010001000001000100000111010111110101110111110101010111110101010101111111010101111111011101011111111101011111110111011111111101010001010000000000010001010100010001010001000001010100000001000100010000010000010001000100000101110101010101111111111101111101010111011111110101111101010111111101111101011101111101011111010101010111000101010001000001000100000101000101000000010000000101010000010001000101010000010001000001010101011111110101111101110111110111110111010101111111011111111101110101110101110101111101111101111111010101110000010000000100000001000100010001010000000101000000010000010000010001010000010000010001000001000111011111111111111111110111010101011101111111010101111101111111111101110101111101111101110101111111111101000000000000010000000001010000010100000101010000010000000101000101010100000100010001010000000001110101111111111101111111111111011111010111110101111101111101010101110101010111011101110101111111110111010100000001000100000000000101000001000100010100010101000100010001010001010100000100010001000100011101011111110101110111111111011101111111010111110101010101111111110101111101011111010111110101010101110000000000010000000000000100000000000001000000010000010000000000000000000100000001000000000100013111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111131111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111121000100000000010000000000000000000001000100010000000000010000000000000001000000000000000100000001110101110111110111011111011111111111110101110101011111110101111111110101111101111111011111010111110111010000000001010000000101000000000101010000010001000100010000000001010100010001000001000101000001011101110111111101011111010111111101010101111101111101010101111111110101110101011101111101110111110101110001000100010001000101010000000100010000010000000101010100010100010000010001000100000001000000010111110101110101011101011101011111111101111101111111110101110101010111011111111101110111110111111111011101010100010100010100000101000101000100000100000100010000010101000100000100010001010000010000000001110101010111011101011111110101010101110111110111010111111111010111011111110101110111011111011111111111010101010100010100010001000101000001000100010001000100000101000000000001010001000100000000010000011101010101011101110101110101110101111111010111111111010111010111111111110101110111010111110111011101110001010100010001010001010001010100000001000001000101010001000001010001010100010001010001010001000111011111010101110111110101110101110111111111110101010101110111010101010101010111011101010111011101011100000001010001000000010001010001000001000001010100010001000101010001000001000001000101000001010101111111111101111111111111011101110111110101010101011111110111011101111111111111111101110111111101011111000000010100000001010001000100000100010101010000010000010100010100000000010000000001000000010100011111011101010101110101010101110111110111010101111111011111011101010111111101111111111111111101011101110001010100010100010101000001000001010001010000010001000100010101010000010001000100010000010000010111011101010111010111010111111111110101111101111101011101011101010101010111110101010101010111110111011101000101010001000001000100000000010000010100010001000100010000010101000001000101010001000000010001110101110101010111111111010111110111111101010111110101111101111111011111010111110101111111110111010111010001010101010000000001000101010000010101010000010100000100000001000001010100010000010001000101011101110101110111011111111111010101010111010101011111010101110111111101111101010111111101010111110101110100010001010001000100000101010101010001010100010001010100010000000101000101000000000101000000010111010111110101011101010111010101010101011101011101011101110111011111110101110111111111110111111111111101000001000100000101000100010001010101000100000101010100010001000001000100000001000001000100010001110101011111011111110111011111011101010101011111110101010111010111110101111101110101110111010101010111010100000101000000010101000000010100010100010000010100010001000001000000010001010001000101010001011101111101010101111111010111011111011111111101011111011111111111110111111101110111110111010101111101110100010101010000010001000101010001000000000100010000000000000001000100010000010001010001010100010111010101110101111101011111010101011101111111111101011111111111110101010101110111010101011101010101011100010100010001010001000001010101000100010000010001000100000001010101010000010001000100010001010101110111010111110101110101111101010101110101011101111101010101110101110111110111011111111101111101010111000101000000000100010000010001010001010001000001000101010101010001000001010001000000010000000100011101110111111111110111111101111101010101111101110111011101010101110111110101011111011101110111111101110100010000000001010001010001000101000100010101000001000101000100010000010101000100010000010000010111010111011111110101010101110101110111110101010111011101110111010111011111010101011101111111011101011101000000010000010001010001010001010001010101000101000101000101010001000001000100010000000100010101110111111111011111111101010101110111010101010101110101110111010101110101111111111101111111110111010111010000000001000000010001010000010001000100010000010100010001010100010001000000010000000100010001011111011111110101111101111101111111011111111111011111011101010111010111110111010111111111010111011101110001000000010000010000000100000001000000000101000001000101010001010001000101000000000100010101000111011101111111111101111111110111110101011111110101111101010101011101010111010111111111011111010101111100010001000100010000000001010100010101000001010100000101010101000101010001000100000000000001010001110101110101010101111111110101010111011101110101011101011101110101110111011101110101111111111101111111010101000101010000010000010101000100010001000100010101000100010101000101000100010100000100010100011111010111110101111101011111010111010101110111111101010101110111010101010101110111010111010101010101110001000000010100010001000101000101010001010000010001010100010001000100010001010101010100010100010111011101111111010111111101110101110101011101011101011111010111011101111111110101010101011111010111011100010000000101000000010001010100010100010001010101000001000001000100000001010100010100000001010001110101011111110111110101110101010111111101111101010101110111111101111101110111010111010111111111010111010101000001000000010001010001010000010000000001010100010000010100010001000001010001000100000101011101010101110111111111110101110101011101111111111101010111010101010101110101111111011111010111010111110101010100000001000100010001010001010001000000000101000101010100010000010100010001000001000101000111010111010101111101010111110101111101110101111111110111110101111111111111010101011101111111010111011101000001010100010101000100010100010001010000010000010000010000000100000101010001000100000101000101111111111101010101010111010111010101010101111101011101011111110111010111010101111101110111010111010111000000000101010001000001000101010001010001000100010101000001000100010001010100010000010001000100011101111111110101111111111111010111111101010101111101010101011111010111111101010111111111011101011101110100000001010100000000000100010000000101010100010101000101000001010000000101000000000101010100010111011101111101011111011111010111011101110101011101010101111101011111011111110111010111110101011101011100010000000100000001000101000001010100010100010101010100000101000000000001000101000000010000010101111101011111111111111111010111111101010111011101010111010111111101111111111111010111111111111111010111000100000000000100000001000101000001000100010001010001000001000100000000000001000100000001000001011101111111111111011101110111010101111111011101110101011111110101110111111111111111011101110101111101110100010000000101000100010001000100000101000001010001000001010101010000000000000101000100000100000111010111011111010101111111011101110111110111110101111111011101010101110101111111110101111111111111111101000001010001000100000001000000010001000100010000000001000101010001010000000000010001000000010001110101111101011111010111111111111111010111010111111111110101110101110101111111111111010101111101010111010000000100000101000001000000000001000101000100000000010100010001010000000000010001000100010001011101111111011111010111110101010111111111010111010111111111010111010101111111111101011111110101111101110001000100010001010001010101010001000101000101000100000100010001010001000001000100000100010000010111010101011101011101010101110111010101010111010111010111011111011111110111011101111111110111111101011101000101000100010001010001000001010100000001000101000100000000000001000100000000000001010100010101110111110111111101111101110111111101011111111111110111011111111111010111010111111111110101010101010111000101000000010000010001010000010100010100000001000100010000010001010101010001000001000100010001011111010111111101010111110101011101011101010111110111011101110101011101010111010101111111110111111101110101000000010101010000010100010101000101010001000100010001010100010001010001010100000000010000000111010111011101011101011111011101010101110101010111011101110111011101110101011101010111111111011111111100000001000101000101000100000101010000010101000100010100010001000100010101000101010000000100000001111111111111110101010101011111110101111111010111010111011101010101011111010101110101011101011111110111000000000000010101010100000000010000000001010101000100010101010101000100010001010100010100000001011101111101111111010101011111111111011111111101010111011101010111010101010111110101011101011111110101110001000100010001010101000000000101000000000101010001000100010001010101000001010101000101000001010111010111110101010111010111111101110101111111110101011101111101011111010101111101010101110111110101011101000100010101000001000000010100010001000100010100000100010100000101010100000101010001010000010001111111010111011101111111111101010111110101010101010111110101011111010101110111110101110101011111110111000001010100010000000100000101010000010100010101010000010100010001010100010001000100010100000000011101110101011101111111010111110101011111011111010101010111111101010101010111011101111111010111111111110001010001010100000001010001000101000101000100010101000000000101010100010000010100000001000100000111010111110101011111111101010111110101110101111111010111110111110111011111111101011101111111010111011101000001010100000000010101000000010100010000010001010001010000010001000000000100000100000101000101111111011101011111111101010111111111010111010111011111010111011111011111110111111111110111010111110111000001000100010001000101000001000000010001000001000001000001000001000000010000000001000101000100011101111101110101110101110111110111011111111111110111011111110101111101111101011101110111010111010101110000010000010001010000010001000100000000000001000001000000010101000100010101010100010001010001010111011101111111110101111111010111011111111111110111111111111111010101010101110101011111011101011101011100010000000000000000000001000001000000000000000000000000000001000100010000000100000000010000000131111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111411111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111200001000000010001000000000100000100000100000001000101000001000001000001000001000000000100000100011111110101111101011101110111010111011101010101110101010101110101110101010101011101011111010101010111110001000100010101000100010001010101000101010100000101010101000101000101010101000100010101010101000111011111110111010101110111011101010101110111011111110101010111110111110101010101111101010111010111011100000001000101010101010000000100010100000001000001000100010000000001010101010100000101000101000001110101110111010101010101111111110111011101111101110111111101011111010101010111010111110111010111110111010101010001010000010000010000000100010100000101000000010101000001010100010001010000000001010000011111010101011101111101111101111111010101110111110111110111011101111111011111011101011111111101011111110001000100010000010100010000000101010000010000010001010001000100000100010001000101000000000101000111011101110101111101110101111111010111011111010101010101011101110111010101011101110111011111110101011101010001010000010000010000000001000100010001010101000101010001010001010000010001010001000001000101110101110111011101111111111111111111011101011101010101110101010101110111111111110101011101111111110111010000000001000001000100000000000101010100010101010100010101010001000001000100010001000000010000011101111111011111110111010111110111010101011111010101010111010101110111110101010111111111111101011111110001000101000001000001010001010001010100000101010101010100010001010001000101000000000000010001000111010101011101110111011101010101111101011111010111011101010111110101010111110101111111111101011111011101000100000001010001000101010000000101000001000100010100000001010001010000010000000001000101000001110111111111111101111101111101111111110101111101011101010111111101111101011111011111111101110111010111010000010001000100000100000000000001010100000100010001000100000001000100000101000000010101000101011101011101010101110111110111111111110101011111111101111101110111110101111111010101111101010111010101110100010101010001010001010001000001010100010000000100010100010000010001000001010100000101000100010111011101010101110101010101011101011101011101011111010101010111111111110111011111010111110101011111011101000100010001010101000100000100010101000100000100010101010000000001000100000001010000010101000001110101111111111101010111110111111101010101111111011111011101011111110111011111111101010111110101111111000100010000010100010001010100000101010000010001000101000101000001000001000000000101000001010001011111010101011101011111010101010111110101111101011101110101110101011111111101111111111111010101110101110001010001010101000001010101000000010100010101000000000100010101000000010000000000000101010001010111111101111101010101110101010111111111010101010111111111110111011101111101011111111111011101110101011100010100010000010001010101000001000101010001000100000000010000000100010001000100010100010001010101110101010101111111110101010111010101010101111111010111110111110111110101111101010101011101110101010111010101010000000001010101000001000101000100000001010000010001010000010000010100010101000100010000011101010101111111110101011111111111110101111111010101111111010101011101111111011111010101110111111101110100010000010001000100000100000001010100000001010000000001010100010001000100010001000100010001000111011111111101110111111101010111111101010111111101111111111101011111110101011101011111010101010111111100010000000100000001000100010000000101000100010100000000010100000100010100000100000100010101000001110101011111110111110101011111011111110111010101011111110101011111010101011111111111011101110111110111010000000000010000010101000100010001000001010101000001010100000100010101010000000100010100010001011111111111111101111101011101011101010111111101110101110101111111011111110101011101011101110111110101110000000100010100010100000100010101010001000000010001000100000100000100010001000101010000010000010111011111010101010101011111110111010101110101111111010111110101011111010111011101110101111111110101011101000000010101010101000001010001010000010100010001000001010100000100010000010101010000000001010101110111111111011101011101110101011101111101010101111101110101011111011111110111010101010111110101010111000100010100010100000100010100010000010101010100010001000101010001000001010001010101010001000101011101010101011101011111110111011101011101010101010101011111110101011101110101011101011101110111110101110100010100010001010000010000010100010101000101010101000000010100010001010100010100010001000001010111011111010101111101011111011111010111010111110101011101111111011101010101111101011101110101111101011100010001010000000000000100010001010001010001000100000100010000010101010000000100010000010000010101111101011111111111111111011101011101011111010111111111111101010111010101111111110111111111011101010111010100000000000000010101000101000100000001000000000000000101010001010000010001000000010001010001011101011111111111111101010101010111111111111111111111011101110101011111111101011101111101011101111101110001000000010001000101000101000100000001000001000100010100010101000000000100010001010101000101000111011111110101011101110111110111010111110101110101010101110111010101111111110101110101010101010101111101000001010001000100000100000101010001000101010101010100010001010100010000010100000100000100010001110111010101111101111111010111110101011111110101010111010111010101010111011111010111110111111111110111000001000100000100010001010000010100000000010001000100010101010101010001000100010001000100000000011101111111110111110101010101011111011111011101111111010111010111010101011101111111010101110111111101110100000000010000010101010101000100000101010000000101000101000101010100000100010001010100010000010111010111111111011111010111010101011111010101011111010111010111010101011111010101011101110111011101011101000000000001010001000001000101000001000100000101010101000100010100010001010100010001010101010001110111111111111101011101111111110101111111011111011101010101011111011101011101011101110101010101111111000100000000000100010100000001010001000101000100010101000100000100010000010100010101010100010001011111010111011111011101110111110101110101110101011101010111111111011101111111011101010101010111010101110001000100000100010000010000010100010000010101000101000000000000000100000001000101000101000101000111011111011111011101111111011101010111111111010101110101111111111111110111111101110101110111010111011100000101000101010100000001000100010000000001010100010100010000000000010100000100010000010100010101111111010101010101010111111111111111010111111101010111010101011101111111010111110111111111011111010111000001000101010101000000000000000101000101000001010100010101000100010000010001000100010000000100011101111111110101010111111111111101110111010101111101011111010111010101011111010101010101011111010111110100010000010101000001000000010100010101000100000100000101000101010100010001000100010101010001010111010111011111010111110101111101010111010111110111111101110111011101011101111111111111010101011101011101000000010001000001010100000100010001000001000000010100010001000101010000010000000001010100010101110111111101011101110101110111011111010111110111111101010111010101110101111101011111111101011101010111010001000100010001010000010001000001010001000001000100000101010100010000010001000000000101000100011101010111110101111101111111011101111101110111110101111111110111010111010111111101111111110101111101110101000001010001000001000101000000010000000101010001000001000101000101000000000101000001000100000111010111110111110101011101010101111101111111010101110101110111010111010111110111110101110101110111111100010001010000010101000100010001000100000100010001000101000100000101000100010001000001010100010001111111010101011111011101111111111101110101110111010111110111011111110111110111010101111101010111010111010001010101000100010000010000000101010000010001000001000001000000010001010001000101000101010001011101011101010111010101111101110111110101111111011111011101111101111111010101011111110101110101110101110001000101000100010000010100010000010100000100000101000100000100000001000101000000010000010001010111011101110111011111010111010111010111010111011111010101111101110111111111110101110101111111110111011101010001010001000101000101010101000001010000000101010000010100010000000001010001010100000001010001110101110101011101010111010101010111111111011101110101111101010111110111010101111101110111110101010111010001000100000101010001000100010000000001000100010100010001010001000101010000010000010001010001011101010111111111110101011111110111011101110111110111011101111101010111010101111101011111010101111101110001010001000100010100000001010101000100010000010000000001000001010101010000010100010001000000010111111101010101010111011111010101010101110111111111111111110111111101010101011111011111011101111111011100010101000101010000000101010100010100000100000000010001010000000100010101000000000001000100000101110111010111110101111111010111011111011101111111111101011101011111110111010101111111111111010111111111000001010000010001000101000100000100010100000000010100000001000000010001010100010000000101010001011101111101110111110101010111011111010101110111111101011101111111111101011111011101011111011101010101110001000001000100010101010100000101010100010000000100010101000100010100000000000101000100000101000111110111110111010111010101011101110101010111011111011101010101010101011111111111010111011111110111011101000000010001010101000100010000010100010001000101010100010100010101000001000001010001000100010001110111111111011101010111111101111111111111011101110101011111011111011101110111111101010101010111011111000000000000000100000000000000000000000001000000000100000000000100000001000000000001000100010000311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111115111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112000010000000000000100000000010000010000000000000001000100000000000100000000000100010000000000000111111101111111110111110111011101011101011111011111110101010111111101110111110111010101011111111111011100010000000001000000000101000101000100010001000101010100010000000100010001000101010101000100010001110111111111110101111111010101110101110101111101010101011111011111110111010111010111010111010101010111000000000100010100010001010000010001010000000101000100010001000000010001000001000001000001010001011101110111110111110101110101111111110101111111110101111101111101111111011111011111111111110101111101110001000000010001010001010100010001010000010001010000000100010000000101000001000000000000010001000111110111111111010101110111010101010101111111010101111111110101111111010111011101111111111111110101111101010000010001010101000001010001000100000001010000010000010001000001000100010100010000010000010001110101010101011101010101111111011111110111111101011101011111110101111111011111010101010101011111110111000101010001010101000100000100000000010001000100010001000100010101000001000001010001010101000000011101111101111101010111110111011111111111010101111101111101010111010101111101111111110101110111111111110000010100010001000000000101000100010001010100000100010100010001010000000100000001010001000100000111111101010111011101111111110101010101011111010111110101011101011101111111110111110111010111010111011100010001000101000100010001000101010100010001010100010101000100010000010001000101000101000101010001110101111101010111110101010101110101011101011101010111010111111101011101010111010111010101010101010111010001000100010000010001010100010101000100010001010000010000010001000001000101010001010101010101011111011101111111011111111101110111010101011101111101111111011101110111111111010101011101010101010111110001000100000001000100010001010001000101010100010100000000010000010000010101010101000101010001000111011101111101011101011101110101010111110101010101010111111111011111011101010101010111110101111111011100000100010101000100000001000101000100000101010100010001000101000001000100010101000000010001000101110111110101110101111111111111110111011111010101010111010101011101111101110111010111111111110101010111010000010001010001000000000001010100010001010101000001010100000100010100000001000001000000010100011101011111110101110101111101111101011101110101010111111101011111110111010111111111011101111111011101110001000001010001000001010000000100010001010001010000010101000000010001010001000100000000000101000111111101110101010111110101111111110101110111111101011101110111110111011101010101011111111111110101111101000101000101000101000100000000010001000000010101010001000001000100010101000100010001000001010001110101110111111111010111011111111101110111011111010101110111110111011101110111111101010101110101110111000100000000000101000100000100010100000100010001010000000000010000010000010000010001000100010100011101111111011111010111011111010101110111011101011101111111111111010111111111011111111111110111010111110000000001000001000100000100010000010001010001000000000001000001010000000000000001000001010001010111111111111101111111010101111111111111011101111101111111110101011111011111111111110101010101011101011100000000010100000001010000000100000100000100000100010000010101000100010000000101010101010101000001110111011111011101111111010111110101111111011111011101011111011101011101011111010101010111010111110111010001000100000100000101000100010000000100000100010100010100000100000001000001010001010001010001011111010101011111110101011111010111111111011111011101011101010111111111111111110101111101011101010111110001010100000000010100000101010001000000010001000000010100000100000000010001000000010101000001000111011111011111011111011111010101011101111101011111111101011111110111111101010111111101010101111111011101000001000100000101000001010100010000010101000001000101000000000000010101000100010100010000000101110101111101011101110101111101011101111101110101010111110101111111111111010111010101110111111101110111010000010101000100010100000100000001010000010101000001000000010100000100000100010001010001000100011101111101010111110111011101011111110101111111110111110101111101010111011111011111110101011101110111110100000101000000010100000100010001000100000000010100010100010001010100010001000000010100000001000111010111110111111111011111111101010111010111011111010111110101111101011101111101111111011111111111011100000001010100000100000000000101000101000101000100000000010001000100010100000100010001000001000001111111111101010101110111111111111101110101011101011111111111110101110101010111110101011101110101111111000000010100010001000100000100000100010101000101000100000000000100010101010000010001000101010000011101111101011111110111010111010111010111010101110101011111111111111111010101111101111101110101011101110001000001000001000100010101010001010001000100010101000000010000010001010000010000000100010100010111010111111101110111011111010101111101111101110101010101111101011101011101011101111111110101011101011101000000000001000100000001010000010000010001010101000000010101010101000101010001000000010100010101110111111111111111010101111101111101111101110101110111111111010101010101110101110111111101011101010111010100000000000001010000010100000101000100010000010000000001010000010001010001000100010101000101011101010111111101111101111101010111010101111111011111011111111101111101110101011111010101010101111101110101000001000100010000010101010101010001000101010001000000000000010101010001000001010001010000000111010111110101110101011111010101010101110101010101011111111111110101010101111101111101111101111111011100000001010001010101000001010100000001000101000101000001000001010100010000000100000101000000000101111111110101110101010101111101011111110111110111010101110101110111011111111111111101110101111111110111000100010001010101010100000100000100010001010001010101000001010001000000010000000101000101000001011101110111110111010101010111111111010111110101111101010111111101011101110101011111110101110101110101110100010001000001010100000000000001010000010000010000000001000100010001010001000001000100010001000111010111110111111101011111111111111101110111111101111111110101111101011101111111110101111101110111111100010000000100000101000000000100000100010000010000010000010000010001000100000000010100000001000001110111011111010111011101111111010111110101011101111101111111111101011101110111111101010111111111110111010000010101000101000101000001000000010100010000010100010000010101000100010100000101010000000001011101111101010111011101110101111111111111111101111101010101011101010101111101010111110101011111011101110001000101000100010000010001000000010000010100010001010001010001010001000100010000000101000100000111110101110111011101111101110101111101011101010101111101111101111101110101110111011111110101011111111101000101000001010001000101000100010001010001010000000100000001000101010100010001000100010101000001110111110101111101011101110111111101111101111101110111111111110101110101011111011111010111010101011111010000010000000100000100000000000100010000010101000100000000010100010100000101000001000001010100011101011101111111011111110111111101010101011101010111010101111111010111010111010101110111111101111101110000010000000101000001000001000101010101010001000101010100000001000101000100000100000001010100000111011111110111010101010111111101110101010101111101010101010111111111010111111111111111110101010111111100010001000101010101010000000100010101010000000101010101010000000001010000000100010000000101000101111111010111110101110101011111110111011101011111011101011101011111111101011111010101111111110111010111000101000001010000010001000001010000010100010001000101000100010000000100010100010000010001010001011101010111110101111111111101110101111101011101011101110101111101011111111101011111111101010101011101110100010001010000000000010001000100010000000100010100010000010100000000010000010000010001000100010111011111110101011111111101110111110101111111111101010111111101011111110111111101110111111111111101011101000001000100010000010001010100010001000001000101000001000100000001000000010001000000000000010101110101110111010101011101011101010101110101110111110101110101110101110111111101110111110111111101010111000101000101010000010101000100010001010001000000010100010001010101010000010000010000010000010001011101110111010111111111011101110111110101110111111111010111110111010101011101111111011111010101111101110000010101000000000001000100000100010001000001000101000001000001000100010000000001000101010100010111111101010111111111111101110111110111110101110111010111010111111101111101111111011101011101011101011100010101000000000100000100010001010001010001000100000101010000010000010000010001000101000100000101111101010111111111010111111111010101110101111111011111110111010111111101111101011101110101110111110111000100010000000100010000000001010001010100000101000100010001010000000101000100010100000100010000011101111101010111111111110111111101010101010111010101010101011101011111110101111101011111110111011111110100010101010000000001000100000101010000010001010101010101000100010100000101000100010001010001003111010101010101011101110111010111111101111111011101010101110101011101010111110101110101010101011101111100010001010001000101000101000000010000000101000101000100010100010100000000010100010001010101000001110111111111011101110111010111111101111101010101110111010111011111011111111111010111111101110101110111010001000100010100000001000001010000010101010001010001010100000100000001000001010001000100010001011101010101011111010111111111110101111101110101110101111101011111011111110101111101110101110111111101110001000100000001000000000000010000000000010000010000000000000100000000000100000000010000000000000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111161111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111121000000000001000000010000000000000001000000000000000001000000010000000000000100010000000000000001110101111111110111011101111101111111110111111101111111110111011101011111011111010101010111110111110111010000000001000100010000010101000001010000000100000001000001010100010001000001010101000100010001011101111111110111010101111101010101010101011111110111110111111101011111011101111101010111011111010111110001000000010101010100010001000101010001000001000001000000000100000100010100010101010100000001000111110101111111010111010101111111110101111101111111110111111101111111011101110101010101011111111111011100010100010001000001010001000000010000010001000100010000010001000001000100010101010000000001000101110111010101110111111101111101011111111101110101010111011101110101111101010111010101111111110101010111000101010100000101000100000101000100010100010101010101000001000101000101000100010000010001000101011111010101010111010101010111110101010101010111010101010101110111110101011111011111010111010111110101110101000101010000010100010001010100010000010001000101010100010001000101000101000101010001010000010111010111110101111111011111110101011111111111011111110101011111010101110101010101010111011101011111011100010001010100000000000000010101000100010001010000000100000001000101000100010101000000010100000101110111010101010111111111111101010101011101011101011111111111111111110111111111110111111111011101110111010001000101000100000001000101000100000100010001000000000100010000010000000000010000000100000100011101011111110101110111110101110101111111011101011101111111010101011101110111110111011111011111010101110100010001000100010000010001010100000101000100010001000101010001010001010000010001000100000101010111010101010111110111111101111101010111011101111101110101010101111101110101111111011101111111011101011101010001010000010000010000000101010100000100010100010100010100010001010000010001010000000100000101110111011101011111011101111111110101011111110111010111011111010101110101111101011101011111011111110111000101000100000000010001000100010000010000010001000100000101010000010000010100010100010000010100011111010101111101111101110101010111111101011111011111011111010101111101111101011101011101011101010111110001010100010100010001010100000100000101000001000001000100010100010000010100010100000100010001010111011101010101110101110101111111010111110101111101111101011111010101011111011101011111011101111101011100010100010001010001010000010001010001000100000100000100010100010101000101000100000100010000000001111101111101110101110101111101111101010101111111010111111101010111011101010101111111011111110111110111010000010001000001010100000100000101010100000100000000010100010001000100010000000101000001010001011101111101111111111101110111010111110101011101011111011111010111010101111111111111010101110111010101110000010100000000000100010001010001010100000100010101000001010001010001000000010001000101000101010111011101010111111111110111011101010101111111111101010101111111011101110111011101010111110111010101011101000100010000000100010101010001010100000000010100010100000001010001000101000101010000000100010101110111111111011111010101010101111101010111010111011111010111111101110111010101110101110111011111010111010000010001000001010101000000010101010001010001000001000001000001000100010000010001010101000001011101011101010111011101010101111111010101010111011101111101110101111101111111111111110101010101111111110001010101000100010101000100000001000101010001000001010100010000000100000000000001010100010000000111011101010111011101010111010111111111110111011101110101010111111111110111110111111101011111111111011101000100010001010101000101010000000001000001000100010001000000000000010001000000000001000000000001110101011111011101011111011101010111110111011101110111110111111111011111011111111111111101111111110111010100000101000001000101000101010001000101000001010001010000000101000100000000000100000100000000011101111111010111011101010101111101010111010111111101010111011111010101011101010111110111111111011111110000010001000101000100010000000101010001000000010001010000000101000100010101010001010001000101000111111101011111010111011111111111110111011111111101011101011111110111111101010111010101010101010111011100010001000001000001000000000000010001000001000101000100010000010100000101000101010001000101000001110101111101110111111101110111011111011101110101111101110111011111010111111111010101111111110111110111010100010001010001000101010001000100000101010000010100010001000100000100000101010001000001010000011101010101110101010101110101111101011111110101111101010111011101011111010111010101110101110101011111110100010000010101000000010001000100010000010101000100000100000100010001000100010100010001000101000111011111111111110111111101110101111101011101010101111111111111111101011111011111010111110101111101011100000000010000010000010001000100010101010001010000010000000001000100010001000101000000010100000101110111111101011111011101111111010101010101111101111101011111110101111101010101010101111111010111110111010001000100010001000100000101010001010001000000010101000100010100010101010100010100000101010001011111010101111101011101110111011101110101010101111111010111010111010101010101011111110111011101010101110001000100010101000100010000000101010001010000000001000101010001010101010100000100010100000001010111010111110101010111010111111111110101111101011111111111010101110101010101111111010111011111111111011101010001010001000101000000000100010100010100010001000001010001010101010100000100010000010000010001110111010101111111010111011111010101011101011101010101111101110101110101010101111111010111011101010111010001000000010001000101000001010000000101000001010100000001010001000100010000000101010001010101011101011111111111011111011101111111111111010101111101010111110101110101111111010111010111011101010101110001000100000001000101000100010000010001010100010001000001000000010000000101010101010001000101010111011101110111111101110101110101011101111101110101011111011111111111111111011101010101011101110101011101000100010000010001010100010100010100010100010101000101000100000000010001000101000100010000010101110111010111111101010101010111011101010101010111011101011101010111010111011101110111011101011111010111000001000000010001000101000100000100010001010001000100000101010001010001000100000101000100010001011111110111111101110111110111011111111111111101011101111111110111011101011111010101110101111101110101110000010000010001010000000100000100000000000100000100000001000100010101000001010100010000010000010111011111110111110101011101111111011101111111111111110111110111010101110101111101110111111101111111011100000001000100010101000100000001000100000100000000000101000101010001000101000100010000010001000101111111110101010111010101110111111101110111011111111111010111010111110111110101010111111101110101110111000001010101010001010100010000010000000100000001000101000100000001000000000100000100000001010100011101111101110101011101110111110101111111110111110101010101111111110111111111011111010111011101010111110001000100010100000100010001010100010001000001000101010000010001010000000101000101010001000101000111010101110111010111110111010101010101010111110111110101110111010101011111011101010101111101110111011101010100010001010000010001000100010001000001010100010000010001010100010100000101000100000100000101110101010101011101011111011111111111111111110101010111011111011101011101011111110111010111110101110111010001010101000100010000000000000000000001010001010001000001000100010100000001010001000101010001011101111101110101111101111111111111110111110101111101111101111101111101011101011101111111010101110101110000010100010001010000010000000001000100010000000100010001000100010100010101000000000001000001000111111101010111110101111101011111110111010111111111010101110101110111010101010101111111111111111101111100010001000001000100000100000100000101000000000101010000010100000101010101000100000000000000010101110101111111010101110111111101011111011111111101011101111111010111010111011111110111111111111101010111010000000101010100010000010100010001000000010100000100010001000100000001000001000000010100000101011101111111011101110111010101011101011101111101011111110101011111111111111101110111111101010111110101110100010000000100010001010101000101000100010101000000010101000100000001000101000001000101010001010111010101111111110111011101011101110101111101011101111111010101010111110101110101111101110101010101011100010000000001010000010100010101010100000100010100010001000100010001000100010100010000010101010101110111111111110101111111011101010101010111111101011101011101111111110111110111010101110111010111010111010000000100010000000001010101000101010000010101000100010001000000000100000101010100010001010001011101010111010101111111111101010111010101010111010101111101110101111111011111010101010111011101011101110101000101010001000000010001000100010001000001010000000101000100000100000001000100000101000101000111011111010101110101111111011111011111011111111101011111110111110101010111111111011111110101110101011100000001010001010100000100000001000001000100000100010000000100010101010000000100010000010001000101111111111111110101010111011111111101111101011111011101111111010111011101011111011111011111010111110111000001000000010001000100000000000100000100000001010100010001000100000100010101000101010001000001011101110101111111011111011111111111111101111111111101010101011101111101111101010101010101011111011101110100000100010001000101000000000000000101000100000100010100000100010000010100010100010100010001000111011111110101111101010111111101111111110101010101111111011111110101111111010111011111011101011101111100000000010000000100000000000100000000000100010000000000000000010000000001000001000000000100000031111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111711111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111210001000000010000000000000000000100000000010000000001000000010001000001000000000001000000000000011101110101110111011111111111011101010101111101011101110111110101010101011101011111110111111101111101110100010101000100000100000101000101010101000101000101000001010001000101000100000001000100010001000111010111010111011101110111010101110111010101111101110111110111111101110101111111110111010101111101011101000001000101000100010001010101000101010100000100010001000100010100010001000001010000010000000101110111110101010101110111011111010111010101010101110101010111010101110101110111110101111111111111110111010001000101010100010100000001000101010001010100010001000001010000010100010000010100000000000001011101010101111101010111011111111101010101110111011101111111011101011111110111011101010111111111110101110001010100000101000100000000000101010001000100010101000100000101000000010001010101000001000001010111111101010111110111010111110111011101010111011101010101011111111101111111011101010111110101111101011101000101000000010101010001010001000101000100010101010100000000000001000001000101000000000100010101110101111101111111010101010101011101111111011101010101011111111111110101111101010111111111110101010111000100010001000001010001010101000100000001000001010101000001000001000100000100010000000000010101011101110101110111010101110111011101110111011111111101010111011101110111111101111111011111111111010101110100010001000101010001010001000000010001000001000001000001000101000000010000010001000001000001010111010111110111010101110101011101111111111101110101111111011101110111111101111111011111010101111101011100010000010100010101010100000101000000000001010101000001000100000000010100000101000001010001000101111111011111011111010101111111010101111111111101010101111101111111110101010111010101011111110101010111000100000100000100010100000100010100000100000100010001010001000001010100010001010101000000010101011101011111011111010111010111011111010111110111111101110101110101110101111111011101010101111111110101110100000100000101010001000100000101010001000100010001010001000001010100010001000101010101000000010111011111011111010101011111011111010101010111010101011101110111110101010101011101110101010101011111011100000100000101010100000001000100010001010001010101000000010001010100010100000101010001000101000001111111110101110101011111111101111111111101010101011101111111010111011111011111110101111111010101111111000000010100010000000100000000000000000101010100000001000001000100010000010000000100000101010100011101111111010111111111011111011111110111110111011111111101111111010101011111011111110111011101011101110001000001010000010100000100000101000001000001000000000101000001010100000001000001000100000100010111010111011101011101011111011111010111110111110101111111110101111111010111111101110101011111111101011101000100010001000100000101000001010000010001010001000000010100000101000100000001000101000001010001110111011111111101111101110111011101011101010111010111011111011101010111011111110111110111010101110111010101000000010000010001000100000101000101000101010001000001000100010100000001010001010001000001011101010101011111111101110111011111010101110111010101010101111101111111011111110101011101010111110101110001010100000000010001000000010001010100010001010101010100000100000001000001010001000101010001010111111101011111110111110101111101111101010111011111010111010111010111111101010101111101110111010111011100010101000101000000010100010001000101010101000001010001000101010000000101010000000100000001010001110101010101010111111111110101110101011101010111011101011111110101011111110101111111110111111101011111010101000101000001000100010001000101000101010001010001000100010000000100010100010001010000010100011101010111110111010101010111110111111101110101011101011101010111011111110111110101010101011101011101110100000101010001010101010100010000000100010001010001000101000101000000010000010001010101000100000111011111010101011101010101010111011111110101111101011101110111010101111101011111111101010101110111111100010000010101000101000100010001000000010001000001000101000001010001000101010000010001010100010001110101111111010101110111110111011111010111111101111101110111111101110111010101011101111101010111010111010100010001010001010001010001000101010000010001000100000100000101000101010001000100000101010001011101010101011101110101110101010101011101011101110111011111010111110111010101111101110111110111011101110100010100010101010001010101000101000101000001010001000001000000010101010000000100010001000101000111111111011101010101110101011111110101110101011101011101110101111101010111110111110111010111010101011100010000010001010000010100010000010000010101000101000100010100010001000001010001010001000100010101110101011111111101111111011101011111011111010101110101111111010101111111011101010101011111011111011111010100000000010000010000010100010101000101010100010000000001010000000100000101000100010001000100011101011101011101110101111101011101010101110101010111011111111101111111010111110111111101011101011101110100010100010001010000000100010100010100010101010000010001010100000101010000010000000100010100010111011101011101110101111101111101010111010111110101111101010101010111010111011111011111111101110101011101010101000101010100000100010101000101000000010001000101010101000101000101000001000000010000010101110101011101110101010111110101010111010111111111110101110101010111010111010101111101110111110111110111010000000100010101000100010100010100000000000100010001010001010001000100000100010101000000010001011101111111111101010111110111011111011111111111010111110101111101011111111111110111010111111111010101110001000100010001010001000100000000010000000101010100010001000101000000000100010000000001000001000111110101010101011101010111011111011111010111110101010111010101110101111111010111011111111101111111011100010100010100010001010001000100000101000001010101000101010000010000010101000001010000000100000001110111011111011101111101011111011111010111110101010111011101111101111101010101111101011111111111111111010001000001000100000100000100010001010001000101000100000000010000010101010001000100000100000000011101011101111101110101111111010111011101011111110101111101111111110111010101110111011111010111111101110100010100010000010100000000010001000101000000010000000100010000010001010100000000010101010001000111011101010111111111010111111111011101110101011111111111110101011111011101010111111101010101010101111100000101000000000001000101000001000100010100010000010001010000000101010001000100010001000101010001111111110111110111111111010101110101111101011101011101010101111111010101011111110101111111010111110111000000010001010000010001010001010000010000010001000101000100010001010001000001010000000100010001011101111101010111011101011101110111111101111111111101110111110101111101011101110101111111011111010101110001000101000001010001000001010000010000000000010000010100010000000100000101000100000100010001000111010101110111111101111101111101011101111111111101011111010111111111111111110111110111111101011111011101010001010000000001000000010001010001000001000101000001000001000100000100000101000000000100000101110101111101011101110101111101111101011101110101110101110111110101010111010101010101111111111111010111010100000100010100010000010000000101000100010001010001000100010101010100010101010100010000000101011111010111111111010111111101111111010101110111110101110111110111011101011111010101010101111101010111110001000000000101000000010000010001010101000000010000010000010100010101000001000100010001000101000111011111111111010111111101111111010101010111111111111101011111010101010101110111111111110101110111011100000000000101000000010000000001010100010100000000010100010000010001010001010000000100010101010001110111011111110101111101111111111101011101010101111101011101011111111101110111010101110111010101010111010100000000010100010100000001000100000101010100010101000100010000010100010001010100010001010101011101011111111111110101010111111101111111110101010101010101111101010101010111011101110111011101010101110100010000000001010001000001000100000001000101010101010001010101010101000000010100010001000100010111010101011111010101111111110101110101110101110101010111110101011101010111111111010111011101011111011101010100010101010100000100010100010100010100010100000000010001000100010001000101010001010100000001110111011101010101010111010111010111010111110111111111111111011101111101010101010101011101011111111111000101000001010101010001000001010001010001000000010000000101000000010101000100010001000101000001011111010101111101010101011101111101011101010111111101011111110111110101110101111101111111010111010101110101010001000101000101010001000101010001000000000100000000010001010100010100010100000001010001000111010101110101110101110101110111110101111111111111110111111111010111010111110101110101111101011111011101010001010100010001010001010000010000000000000001010000000001010001000000010001010000010100010001110101010101010111011101010101011111011101111111110101011111111101011111111111110101111101010101111111010101000101000101000101010100010001010000000100010101000001010100010000010001010000010001010000011101011111110111010101110101011101011101111111011111010111010101011101010111010101111101111111111101110100000001000101010100010101000100010000000100000101010001000100010001000101000100000100000001000111011111110111010111010101110101111101110111011111010101011111111101011111010111110111111101110101011100010001000001000001010001000100010000010101000101000100000000010100000101010001010000000101010101110101010111111111111101110111110111111111010111010111110111111101011111110101010101111101110101010111010001000000000000000001000000000000000000000001000000000000010000000000010001000000000100000001311111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111118111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112101000001000001010000010000000000000001000000000000000000010000000000010000000000010000000000000111010101010101110101010111011111011111111101111111111111110111011111111101010111111101011111111111011101010101000100010101000001000100000000010001000100000001000000010000010001010000000101000000010001110101010111110111010111111111011111111101110101010111110111111111011101011101110111111101111101010111010001010001000001010000000000000100010000010101010001000100000101000100010001000000010100000101011101111101010111111101011111111111010101111111010101011111010111010101111111110111111101010111110101110001000101000000000001000000000100010000000001010100000001010101010000000001000001000101000100010111110101110111111111111101111111111111111101111101011111111101010101111111110101110101110111010111011101010100000000000100010000000000000000000100010001000000000101000101000000010001010100010001000101110101010111111111110101011111111111111111110101111101111111110111110101111111110101011101011111010111000100010000000001010101000001000000000001010001000100000100010000010000000101010100010100000001011101110111011111110101010101110101111111110101110101011111010101010111111111010101011101011111111101110100000100010000010101010001010000000100010001000101000100010001000000000001000100010100010000000111011111011101110111010101110111111101011101110111110101011101111111111111111111111101010101110111111100010000010001000001010000010000010100010001010001010100010100010001000000000100000101010001010001111101011111110111111101111101011101111101110101010111011101010101010111111101010111110111110101110111000101000000010000010100000101000000000101010101000001010101010001000100000101010001000001010100011101111101111111011111010111110111111111110101010111111101010101111111010111110101110111110101010111110001000100000100000001000001000100010000010101000100000101000100000001000001000100010001000101000111110101110111010111111101111111010101110101010111010101110101111101111111110111110101011111110111011100010100000101010000010100000100010001010101000001010001010100010000000001000001010001000100000001110111011111011101011101010111011111110101010111110101110101110101111111110111110101111101010111110111000100010001000101000101000101000000010101000001010100010100010000010100010001010000000101010001011111010101010101110111110111010101111111110111110101110101010111111101010111010101110111110101010111110001010101010100010001010101000100010000000001010000010100010001000100000001010001010001000101000111011111010111010111010101010111110111010111110101111111011111010101111111111101110101110111110111011101000001000001010001000001010001000101000001010001000001000001010100010000000100010001000001010101110101111101111101011111111101110101010111110111110101111101111101010101110111110111110111110101010111000100000100000100010000010001010100010100010000010100010001000100010001000001000101000000010101011111110111111111011101011101010101011111010111011111110101110101110111110111110111010111111101010101110100010000000100000101010101010100010001000001000000010001010001000001010001000101000000010100010111010111010111010111110101011101011101010111111101110111110101110111110101010111010101111101011101011100010001000101000001010100000100010101010001000100010000010100000001010101000101010100000100010101110111011111010111111101011111110111010101110101110111011111011111110101011111010101011101111101010111000100010001000001000100000001000001010000010001000101000000000100010100000101010100010100000101011111011101011111110101111101110101111101111101011111010111110111011101011111010101010101110111110101110001000100000100010000010001010100000001000101000001000001000100010100010001010001010001000100010111011101111111010111111101110101010111110101110101111111110111111101010111011101111101110111010111011100010000000101000000010100010001000101010100010000010001000000010101010001000001000101010001010101111101111111110111111101010111110111010101110111111101010101111101010111011101111101110101011101010111000100010000010100010101010001010000010000000100000101000100010001000101010000000000010000010001011101110101011111010101010111010101111101111111010111110111110101111111010101011111111101111111110101110000010101010000010001010001010001000100000101000100000100010001000100010001000100000000010000010111111111010101011111111101011101110111110111010111011111110111110101111111011101011111110111011111011100000100010001000000010001000101000001010001000100010001000001010000000001000100000100010000010001110111011111011111011101111101110111110101011111011101010111110101111111011101111111011111011111010111000100000100000001010000010100010001000101000101010001010001010000000101000100000100010001000101011111011111011111111101111101010111010111110101010101111101010101111111011101111111011101011101010111110100000100000000000100010001010001000001010101010000010101000100010100010001000100010101010101000111011111011111111111010101111101011101110101010101110101010111110101011101110101011101010101010111011100010001000000000101010000000101010100010001010000010101010000010001010000010101000100000101000101111101011111110101010101110111010101011101111101111111010101110111110101111111010101011111110111010111000101000001010101000100010001000100010000010000010001010001010001000100000001000101000100010001011101010101110101011111110101111101111101111101111101011101110101110111011101111111110101010111110101110101000100010100000100010100000100000101000101000101000101010100010001000100000001000101000001010111011111110111111101010111110111110111110101110101111101010101010111011101110101111111110111110101011100000000010000000101000100010001010001010100010000010101010001000001000100010100000001010000010101110111111111110111110111010111010101010101010101111101010101111101111101011111010111010101011111010111010000000000010001010100010001010001010000010001000101010000010100000100010001000101010101000101011101011111111111010101011111111101111101111111111101110101111101011111111101011111010111010101010101110001000000000101000100000000000000010000000000000100010000000100010000000100010001000001010100010111111101011111110111111111011111110111111111111111111101111111111101011111111101011111111101111101011100000101000001000100000100010000010001000001000000010000000000010101000000000100000101000100010001110111110101110111010111011101111111010101011101110101110111111101010101110101111111010101110101111111010001010001010001010000000100000101010100000001010001010001000100010100010100000100010001010100011101010101011101011101111111110111010101011111111101110101010101011111110111010111011101110101010111110101000101000100010000000000010100010001000100000101010101010100010000010101000100010001000101010111010111110101011101011111111111011111111101010111110101010101010111010111010111011101110111110101011101000100010101000100010000010000000001000100010000010100010101010001000100010001010001010001010101111111010111011101111101110101111111010101111111111101011111010101011111011111011101011101011101010111000001000100000100010001010000000101010100000000000100010001010100010001000101000100000101000100011101110111011111110101110101111111010111010111011111011101011101111101011101010101011111110101111101110101000101000100010000010001000000010001000101000001000101010100000100010101010100000000010101000111010101110101110111111111010111111111010111110111111101110101010111111101010101011111011111010101111101010100010000010000000001000000010001010001000000000101010100010100000101010001000001000001010001110101010111011111110111111101111101011111010111111111010101011111010101110101110111111101111101110111010001010001000001000100010100000100000001010000000101010100000101010100010000010000000100000001011101111101011101110111110101110111011111111101011111010101011101010101110111111111011111111111010101110000000101000100010000010000010000000000010000010001010100000100010001010000000100010000000001010111011111110111010111011111111111111111111111110111011101011111111101110101011111011101111101011111011101000001000101000001000000000000010000000001010001010100000100010001010001000101000100010101000001110101110111010111011101111111111101011111110111011101010101010101110101111101110101110101011101111111000101010101010001000100000001000101000001000100010101010101010001010000000100010000010100010100011111110101010101011101110111010101110111010111011101010101011101110101011111110111111111010101010101110000010100000100010100010001010001000101010101000101010100000001000100000000000001000001010001010111111101011111111101011111011111110111010101010101110101011111110111111111111111110101111101111101011100000100000000010100000101000001000101010001010100000101000100000101000100000101010100000001010101110111111111111101011111010101110111010101111101011111011101011111010101010111010101011111110101010111010000000000010100000101010001000001010000010100000100010100010000010100010101000100000100010001011101011111011101011111010101110111111101111101010111011101011101011111011111010111011111010111111101110101010001000101000001010001010000000001000101000100010001010101000001000001000100010001000000010111010101011111010111110101011101111101110101010111111101111101010101111111011111011101011111111101011101010101000101000001010100010000010100010101000000010000010001010001000001000001010100010000010101110101010101010111110101010101111101010111011111111101111101011111110101111101111101011101010111010111010101010101000100010101010000000101010000000100010100000101000100010001000100010001000101000100011101010101010111110111110101111111111101011111010101010111110101010111010101110101111101110111011101110000010001000000000000010000000000000100000100010000010000000100010001000000010000000100003100000111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111191111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111120010001000001000000000000000001000100000100000001000000000000010000000000000101000001000000000001111101010101110101110111111111110101010111010111110101111101111101110111111111010101011101111101110111010101010101000100010001000100010100000101010100010100000100010000010000010001000100000101000100011101010111010111110111011101010111011111110101010111010111111101011111011101011111111101110101110111110101000101010000010100000101000100000100010101000001000001000101000100010100000000010000010100010111010111010101011111010111110101110111110101010111111111110101110101010111011111111101111111010111011100010001000101000001010000010100010000010101000000000100010000010100010001000001000100010001000101110111011111010111010101011101010111011101110111111101010101111101011111011101111101110101011111010111010000000101000101000101000101010101010100010000000101010100010100010001010000000100010001000100011101011111010111011111110101110101010101010111011111111101110101111101011101011111110111111101011101110100010001000100000100010001010101010001010000000100010000010000010101000101000000010000010100010111011111011111011111010111111101010101111101110111010101111111111101010101010101111111111101011101011100000101000000010101000000000100010000010001000100010000000100010001010101000100000000000101010001111111010101111101010111111111011101111101110111111111110101010101111101011111111111011101110101111111000001000100010001000000000100010001000001000000000001010100010101000100000000000101010100010000011101111111110101110111111111011101110101110111111111110101011111010101110101111111010101010111110101110000000000010101010000000100010001010001000100000001010101000001010101010000010100010101000001010111111111111111010101111111011101011101110111110111110101110101111101010101111101011111010111110111011100000100010001000100000001000101000101000001010001000000010001000101000101000100010000010001000001110101110101011101110111111101110101110111110101011111111111110101010101110101110111011111011111110111010100010001000000010000000100010000000101000101000000000101010101010000010001000001000101000000011101110111111101111111011111111111111111010111110101111111010101010101111101110101111101010101111111110001000000010001000001000001000001000001000000010100000101010101010001010101010001000100010100000111010111111101111101111101110101011101111111110111010111010101010101110101010101110101111101010111011101000000010000010000000100010100000100010000010001000101010101010100010001010001010101000100010101110111010111111101011111110101011111110101010111011101011101010101010111011101110101010101111111010111000101010001000100000101010101000000010101010001000100000100010101000101000001010101000100000001011111110111010101111111010101110101111111010101011101111111111101010111010111110101010101111111011101110001000101000100000100010000010000000100010101010100000000010101000101000100010100010000000001000111010111010111111111011101111111111111011111010101011101111101011111010111010111011111111111110101111101000001000000000100000000010000000001000001010101000100000101000001010000010001000100000001010001110111111111111111011111111101011101111111111101010101110111110101111101111111011101110111110101110111000000000000000100000001010001000100000100010101000101010000000100010000000100010000010001010101011101111111111101011111110101110111110111010101010111110101111111110101111111011101111101010101010101110001010000000100010000010000010001010100010001000000000100000000010000000100010000010101010000010111110101011111011111011111111111010101011111111101111111110111111111111111011101111101010101111111011101000101010001000100000000000001000100000000010000010001000100010000000101000100000100010001000001110111010101011101011111111111111111111101111111111101010111010101011111010101110101111111111101111111000101010001000100000000000001000001000100000000010001000100010100010001000100010100010000000100011101110101110101111111111111010101110101110111011111111111010111010111010111110111010101011111110101110000010001010100010000010001000100010001010100010000010001010001010001000000010101010001000000010111011111110111010111011101011111111101110101011101011101011111011101011101111111010101111101011111011100000001000001010001000100000000010001010000010001010001000001000100010100010100010001000101000101111101111101111101011101111111011101110101111101111101111101111101111101110101010111110101110111010111000100010000000101000100000101010001000000010000000001000001010001010000010100010001010100010001011111110101110111110101110101010101110111111101111111110111010101110101111111010111110101110111011101110000010100010001010001010101000001000100010100000001000101010001000100000101000100010001000100000111011111011111010101110111010111111111010111010101111111011101110111010111010111010101110111010111111100010100000101000101000001010000000101000001010000000100000100000101000101010101010001000001010001111101011111010111110111111101011111010111011111111111011111110111010101110101010101110111111101010111000101000001000001000000010001000001000101000000000001000100000101010100010100000100000101000101011101110101111111110101011111110111110111010111011111110111010111011101010101011111111111010101110101110001000100000001010100000000010001000101000001000001000101000101000101010100000000000101010000010111010101110111110101111111111101010111010111111101111111010111010101111101011111111111010101111111011101010000010001010000010000010101010100010000000000000101000001010001000101000000010001000001000101111101111111010101111101011101010101011111111111111101010111111101110101110101111101011111110101010111000100010001010100000100010101010100000000000000010101000000000101010100010100000001000001000101011101110101010101010111111101011101010101111111111101110111111111010101011111011111111111011111110101110000010101010100010000010100000101010000000101000100000000000101010101000100010000000100000000010111011111011101111101011101011111110101111111010101110111011111110101010101011101011111010111111111011100000100010000010101010001000000010100010001000000010001000000000101000100010001000001000100000001111111111101010111010101111101111111010101011101111111111101111111110101111101111101111101110111111111000000000101000101010100000100000001010001000001000100000100000100010100000001010001000100010000011101111111110111010101010111111101111101111111110101010111111101110111110111110101110111110111011101110001000001000100010001000000010000010000000001010100010000000100010000010001010001010000010000010111110111110111011111110111111101111111111111010111011111110111010111010111010101011101011111011101011100010000010000010001000100010000000001000101000101000001000101010001010001010101000100000101010101110111011101011111010111010111111111110101011111010111010111010101111101111101010101111111010101010111000101000101010001000000010001000001000100000101000001010001010000010000010000010000000101010101011101010111110101011111111111010101110101111111010111111101011101111101111101111111110111010101010101110101010001010100010000010001010100010000010001000000010100010000010000010000000001000101010101010111110101010101011101010111011101010111011111011101111101010101011111111101111111011111010101010101111100010001000001000101010001000001010001000101010001010001010101000000010000000100000101010100010001110111011111011101110101011101111101011101010101110101111111011101111101111111011111010111011111110111010001000101000100010100010100010101000101010100010001000001000100010000000101000101000001000000011101110101011101110111011101110101011101110101010111010101011101111101111111010101010111111101111101110001010100000100010000010000010100000101010101010001010100010000000100000100010100010000000100000111110101011111110101111101111111011111110101010101110101111101111111011101111111011101010111111111011100010100010000010100010100000100000100000101010000010000010000000100010000000001000101000001000101110111111101011101010101110111011111011111010101111111111101010101111101011111110101110111110101010111000001000101000101010000010001010001000100010000000100000101010100000101000100010001000001000101011101110101110101111101111111010101011101011111011101110111110101010111110101010111110111011111110101110001000101010000000000010001010100010101000000010100010000010101000100000101010001010001000000010111110111110101111111111101011101011101010101111111010111011111011111011111111101010101011101111111011101010000010101000001000101000100010001010000010001000100000100000100010000000101000101000101000001110101111101010101110111010111010111111101111101011111011111011111011101011111110111110101110101111111010000010100010001000101000101000001000100000100000100010101010001000101000100010001010100000001011101111101011101110111011111010111010101110111111111011101010101010101110101010111010111011111110101110001000100010100010001000001000001010101010000000001000100010101010000010101000001000101000001000111010101111101010111011101111111110111010101011111110101111101010101111111010111111111010101110111011101010100010101010100000100010000010001000101000100010100010001010000000101000001000101000101010001110101010101010101011111111101011111010111110101011111010101111101111111010101110101110101110101110111010100010100010100000000000101000101010001000100000000010000000100000001010001000100010000010001011101111111010111010111111101110101010111010111111101111111110111111101111101110111110111111111010101110100000001000101010000010100010101010001010000010000010001010000010100010001000001000100000101010111010111111111110101011101010111010101011101011101111111010111011101110101110111110111010111011101011100000000000000010001000100000001010000010000010000000001000000010000010000000001000000010000000131111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111101111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111121000001000000000000000100000000000000010001000000010000000100000000000001000100000000000001000001110111010101111111011111110101111111111101010111110101111101110101110111111101010101111111110111110111000101000100010100010000010100000000010001000001010000010000010100010000000100010000010001000001011111010111110101011101011111011101111101111111110101111101111111011111011111111111011101110111110101110101010000010101000101000100010100010100000001010000010100000001000000000100000101000100010001000111010101111101010101110111011101011101010111011101011101010111111101111111110111011101110101010111011100010000000101010001000101000100000100010001000101010100010000000101000000010100010100010001000101110111111111110101110111010101111111011111011101110101011101011111110101111111011101010111111111010111000100000001010001000000010000010100000101000100000101000101010000010100000000010001010100000001011111010111110101010111111101111101011111010101110111110111110101011101011111110111111101010111111101110100010000010001010000010001000100000101000100010001000000010101000101000001000000000100010000000111011111011111111101011101011101111111010111111111010101111111010101110101110111011101111101011111111100000101000000010100010101000100000001000000000001010000010000010001010100000100010100010101000001110111010111011101111101010101110101110111111111111101111101111111110101011111011101010101010111010111010100010001000100000101010001010101010100000100010001010001000100010101000101000101010101000101011101011111011101110111110101110111010101010101010101110101110101010111010101010111110101011111010101110001000001010101000001010100010001010100010101010100010001010101010001010101000000010100000100010111110101111101010101110101010111011101010111010111010111010101010101011101010111111111011111011111011101000101000101010001010101010001010001010001000001000101010001010100010001000000000001000100010001110111110101010101011101011101010101011101011111110111010101111101011101111111011111111101011101011111000001000100010001000101000101010001000101000100010001010000000100010100000101000000000100010000011101011101111111011101110101111101011111110101010111011111111111010101010111010101111111111111111101110101000100000100010101010100000100000000010100010101000000000101010100010101000100010001000000010111010101110111011101010101010101111111111111011111010101111111010111011111010111110101010101111101111101010100010100000101010001010000010000000100010001000100010001010000000001000000010001000000010001111101010111011111110101111111111101011111011101110111110111011101011111110111111111111111111101110111000101010001000000010000000000000101000101010100000100000101010100010000000000010000000000010001011101110101110101110111111111011111010101110101010111110111010101011101111111111101011111111101111101110001010000010100010000000101000101010001010000010001010100010001000100000100000101000000000100000111010101111101011101011111010101010101110101011111010101011111011101010111011111110111111101110111011101010001010100010100010001010100010000010101000001000100000100000101010100000001000000010000010101110101110101011101111101011101011111111101010101111111111111011101111101011111110101111101111111010111010000010001010000000101000101000000000101010001010000000100010100010100000001010000010001000001011101111111011101111111110101011101111111110111110101010111010111010101010111110101111111010111011101110001000100010000000001010100010101000001000000010001010001010001010001000100010100000101000100000111110101011101011111011101011101010101110111011111011101011101011101111111011101010111010111011111111101010100000101000100010100010100010101000100000101000101000101000100000100010100010101010001000001110101011111110101011101011111011101010111011111011101110111010101111101011101011111010111011101110111000100000100000100010100000100000101010001000101000101000100010100000100010100000001000101000001011101111111011111111111011111011111110101011101010101110111010111011101111101011111111111010101111101110100000100000100000100000100010000010101000101010100000001000101000100000001000000000001010101000111010111111111010111011101011101011111010101111101010111111111010101110111111101111111111101010101011101000000000100010100010100010100000001010000000101000100000001010001000100010100010001010001010101110101111111011111011101110101011111110101111111010111011111111101010111110101010101010101011101011111010000000100000000010100010100000000010001000101010000000000000101000100010001010101010100000100011101110111111101111101010111011111111111110101010101111111111111111111010111111101010101010111111101110001010000010100010100010000010000000001000101010000010000000100000001000100000100010100010000010111110111011101010101111101111111011111110111110101011101011111010111111111010111111111010111011101011101000001010100010000000100000001000001000001010100010001000001010000000100010001010001000101010101110111111101010111110111110111111101011111110101011111111101111101011111011111010101011111110101010111010000000101010001010000010001010100000001000100000000000100000101000100000101000100000000010100011101011111010101010111011111010101011101111111111111111111110111110101011101010111011111111111011111110100010100010101000001000101010000010001000000010000000101000100010101000100010101000100000100000111011101011111010111111101010101111111010101011111010111010101010111010101111111010111010111010111111100010000010101000100000101010001000101000101000101000101000101010001010100010000000001010100010001111101111101010111011111010101110101011111010101010111010111110101011111010101011111111101011111110111000100010100010100000101000101000100000101000100000101000001000001000100010101000000010001000001011101011101011101011111010111110111111111011101111111110111110111110101011111011101111101110101110101110100010100010001000001000001000001000100010001000000010001010001010100000100010100010001000100010111011101011101110101111111110101011101011101110101111111110101010111011111010101010101110111110111011101000100010001010100000001010100000101000100010100000000010101000101010001010100010001010000010001110111010111110101010111110101111111110101111111010111111101010111010101011101011111011101011111010111000101000001010100000100010000000001000000000001000001000101000101010101000100000101000101000001011111010101011101111111110111011111110111111111111111110111110101010101010101111111010101010101111101110001010100010001000001010101000001000000000001000000010001010101000100010000010100010101000100010111011101011101110101110101010111011111110111110101110111010101110111110111111101011111010111110111011101010100010001010001000101000101000001010100010001010001010000010001000000010001000101000000010001110101011111110101110111110111010101110101010111010101011101111101010111111101110111010111110111011111010100000001010000010000000100010101010001000101010101010100000101000001010001000001010001010001011101011111110101111111110111111101010101011111010101110101010111110111110101110111111101010101011101110100000001010001000000010000000101010101000001010001000100010100010001010001000000010101000101000111010111110101010111110111011111110101011101111111110111011111010111010101010111111101010111110101011101000001000101000001000100010100010000000100000000000101000001010001010101000000010001010000010101110101111111010111110111011101010111011111111111011111010101010101110101011101111101110111011111010111010100000101000101000101000101000101000000000100000101010101010001010100010100010001010001000001011101110111010111010111010101110111011101111111011111011101110101110101011101010101011101011101011111110100010001010001000100010100000101000100010101010100000000010001000100010100010101000101000101000111010111011101011101111101010111010101110101010101011111111111011111011111011111110101110101110101011101000101000100010001000100010101010100010001000100000000010001000001000100000001000001010001000101110111010101110101010101111111010101010111011111111111111101011101111101011111110111110101111101110111000001010001010101000100000000010001010001000001000100010101000001000100010001000100010100010001011101111101110111010111110111111111111101011101110101010101011101111101111101010101010111010101111101110100000101000001000100010000000101000100010001000101010001000101000100000001010101010001010000000111010111110111011111110111011101010101011111110111110101111101110101111111111101110101011101111111011101000100000101000000010101010100010100000001000001010000000100010001000100000000010100010100000101111111011111010101111111010101011111011111011101111101111111110101110101011111111111111101010111011111000001000100010100000000010100000000000101000100000001000100010001010101000100000000000100000100011101110101011111010111111101011111111111110101110111110101010111110101010101010111111111111111011101110100010100000101010000010000010001000001000001010001000101010001010001000101000100000100000101000111011111011111010101011101111101010101110101111101011111110111010101111111110111011111010101010101011100010001000100010100010000010101000101010001000100000101000001000100000100010001000100010101010101111101011101011111011101111101110111110101111101110101010111111111011111010101011101011111010101010111000100010100000100010100010001010100010001000101010100000001000100000001010100000101000001010101011101111101110111011111011101110101010101110101110101010111111101011111110101111111110101111101010101110100010100010101000100010001010100010001010100010101010001000100000001010000010001010000010101010111010101010111010101011101011101010111011101010101010111010101111101111101111101010101111101011101011100010000010000000100000100000001000100000001010001000001000000010000000000010001000000000100000131111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111
一、递归方式解决，代码如下
#include<stdio.h>int search(int startI,int startJ,int endI,int endJ);char maze[100][101];int success=0;void main(){ int L; //freopen("maze2_test.txt","r",stdin); for(L=0;L<10;L++) { int i,j; int T=0; int result; int startI=0,startJ=0; int endI=0,endJ=0; scanf("%d",&T); for(i=0;i<100;i++) scanf("%s",maze[i]); for(i=0;i<100;i++) for(j=0;j<100;j++) { if(maze[i][j]==‘2‘) { startI=i; startJ=j; } if(maze[i][j]==‘3‘) { endI=i; endJ=j; } } success=0; result=search(startI,startJ,endI,endJ); printf("#%d %d\n",T,result); /*for(i=0;i<16;i++) { printf("%s",maze[i]); printf("\n"); }*/ }}int search(int startI,int startJ,int endI,int endJ){ if(maze[startI][startJ]==‘3‘) success=1; maze[startI][startJ]=‘1‘; if(success==0&&maze[startI+1][startJ]!=‘1‘&&maze[startI+1][startJ]!=‘2‘) search(startI+1,startJ,endI,endJ); if(success==0&&maze[startI][startJ+1]!=‘1‘&&maze[startI+1][startJ]!=‘2‘) search(startI,startJ+1,endI,endJ); if(success==0&&maze[startI-1][startJ]!=‘1‘&&maze[startI+1][startJ]!=‘2‘) search(startI-1,startJ,endI,endJ); if(success==0&&maze[startI][startJ-1]!=‘1‘&&maze[startI+1][startJ]!=‘2‘) search(startI,startJ-1,endI,endJ); if(success==0) maze[startI][startJ]=‘0‘; return success; }
二、利用队列来解决，代码如下
#include<stdio.h>typedef struct node{ int x; int y;}Node;void push(Node shu[10000],Node n);Node pop(Node shu[10000]);int empty(Node shu[10000]);int front=-1;int rear=-1;void main(){ int L,T; freopen("maze2_test_input.txt","r",stdin); //freopen("test.txt","r",stdin); for(L=0;L<10;L++) { int i,j; int result=0; front=-1; rear=-1; Node shu[10000]; Node n; char maze[100][101]; scanf("%d",&T); for(i=0;i<100;i++) scanf("%s",maze[i]); for(i=0;i<100;i++) { for(j=0;j<100;j++) if(maze[i][j]==‘2‘) { n.x=i; n.y=j; push(shu,n); } } while(1) { if(!empty(shu)) { n=pop(shu); Node n1,n2,n3,n4; if(maze[n.x][n.y]==‘3‘) { result=1; break; } maze[n.x][n.y]=‘1‘; if(maze[n.x+1][n.y]!=‘1‘&&maze[n.x+1][n.y]!=‘2‘) { n1.x=n.x+1; n1.y=n.y; push(shu,n1); //printf("(%d,%d) ",n1.x,n1.y); } if(maze[n.x-1][n.y]!=‘1‘&&maze[n.x-1][n.y]!=‘2‘) { n2.x=n.x-1; n2.y=n.y; push(shu,n2); //printf("(%d,%d) ",n2.x,n2.y); } if(maze[n.x][n.y+1]!=‘1‘&&maze[n.x][n.y+1]!=‘2‘) { n3.x=n.x; n3.y=n.y+1; push(shu,n3); //printf("(%d,%d) ",n3.x,n3.y); } if(maze[n.x][n.y-1]!=‘1‘&&maze[n.x][n.y-1]!=‘2‘) { n4.x=n.x; n4.y=n.y-1; push(shu,n4); // printf("(%d,%d) ",n4.x,n4.y); } } else { result=0; break; } } printf("#%d %d\n",T,result); //printf("%d,%d\n",n.x,n.y); }}void push(Node shu[10000],Node n){ rear++; shu[rear].x=n.x; shu[rear].y=n.y;}Node pop(Node shu[10000]){ Node n; if(!empty(shu)) { front++; n.x=shu[front].x; n.y=shu[front].y; } return n;}int empty(Node shu[10000]){ if(front==rear) return 1; return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。