Figure -: 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 00, 0, 0, 0, 0, 0, 0, 0, 0, 00, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 00, 0, 0, 0, 0, 0, 0, 0, 9, 00, 0 0, 0, 0, 0, 0, 0, 0, 0
This is a map of the connected map, assuming the sections 8 and 9 are two identical cards. In the array matrix, 0 means no card, greater than 1 means a card. As for what card, it is random. Don't tell me, what you said is how to put the card just right, that doesn't matter what algorithm, you only need to prepare even a number 1 in the map array, to ensure that each card is even more (Different kinds of cards are represented by greater than 1), and it is possible to put in the position of each 1.
1. Calculate the two cards on the map (Of course, haha).
This is the first step in connecting the path search algorithm. First define the sufficient conditions for two cards to connect: 1. Two cards are the same. 2. There is a full 0 road between the two cards. 3. This road cannot have more than two corners (Corner) to meet these three conditions, you can think that these two cards can be connected.
First, we complete a basic pathfinder algorithm according to the first two conditions. Our goal is to find a way to connect from 8 to 9. So very clearly from 8 to 9, there are four directions, it is the four directions of East, South, West, North (E, S, W, N in China's map direction), in In one step, we must first assume that there is no advantages and disadvantages, then I can choose one direction, that is, the east. Figure 2: 0, 0, 0, 0, 0, 0, 0, 0, 0, 00, 8, 0, 0, 0, 0, 0, 0, 0, 00, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 00, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 00, 0, 0, 0, 0, I moved from 8 to the east, so I arrived at -8 position, I can move to -8 position, it is because 8 The position is originally a 0, indicating that there is no card. So now the problem is turning, how to find connected 9 from -8! It should be understood here, a lot of money, it is a bit like a mother talking.
Therefore, the current path finding algorithm is attributed to the basic problem of a recursive algorithm. First, from 8 to find the next node -8, use the same rule, from -8 to find the next node, such as -88. . . Figure 3: 0, 0, 0, 0, 0, 0, 0, 0, 0, 00, 8, 0, 0, 0, 0, 0, 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 00, 0, 0, 0, 0, 0, 0, 0, 0, 00, 0, 0 , 0, 0, 0, 0, 0, 0, 0, 0, 0, 00, 0, 0, 0, 0, 0, 0, 0, 9, 00 , 0, 0, 0, 0, if it can always be OK, if there is no hindrance, finally found 9, even if it is successful, if you have to go, you will return it again. The node, developing in other directions, there is no, turn back the superior node, then develop in other directions, the logic here is the thought of recursive.
The algorithm written in this way can already be used in the optimal situation, such as from 8, to -88, haha. But in a slightly complex case, a strange recursive node is generated. P4 machine also runs. I tried, haha.
Then the second step is to weigh the four directions of (e, s, w, n), which is to have a priority between them. White is the road to try. The rules of the decision should have several, for example, in the No. 9th position, it is in the southeast of the 8th, and the trial road should be prioritized to choose the east and south, and then if the No. 8 is 8 Face, it is of course choosing a positive east. For example, when walking to -8 position, it is obviously only three directions, because it can't be turned back.
After such processing, the number of nodes generated by the recursive algorithm will be significantly less, which will find a successful way. But performance has no essential change in worst cases.
Next, in the third step, we add the third sufficient condition to solve fundamental problems. 3. This road cannot have more than two corner (CORNER)
According to object-oriented ideas, it is natural, I add a Corner's attribute to each of the positions generated in the recursive algorithm to record this path to turn several angles so far. This time I am going to do this. If this node has been turned to two bends, if you want to turn it again, or before you get to 9, it is decisively over, and then the superior node is returned.
Ok, let's talk about it, can't say more, otherwise it is equal to the code, haha. Note that in detail the conditions of the second and three steps, it is possible to make it impossible to improve the node OVER as early as possible, which is the key to improve performance. The stronger your algorithm is, the higher the performance.
Our algorithm is on the machine of 500, 256m, 100,000 averages is no more than 0.1 milliseconds when the operation is spent, and it is not accurate, the speed is really very fast, because in a very bad situation, the maximum knot produced The number of points is 690, which must be very fast, detailed data has not been clear.
Said so much, I should understand the idea of the first step of the intercourse algorithm. I know it as much as possible. This algorithm is completely characterized by the characteristics of the connection, and is done. Because it is a step Test, I personally feel very natural, there is no deep place, after completing, the performance is also very good, this feels so simple. I believe you can write your algorithm to see you. Second, is there any solution to the whole map? ? ? Can I connect to the total number of people? this is a problem. Before resolving this problem, let's solve the prompt function (hint) is to provide a prompt for the player, which pair can be connected. My approach is to bring together the same card in the entire map, and use the array, the list is also. Like this, 4, 4, 4, 4 5, 5, 5, 5 6, 6, 6, 6 ... then calculate which two pairs of two pairs between 4 4, as for how to determine Even, the first step algorithm has been implemented, haha. I found that there is a card that can be returned, telling the player that two cards can be connected! This is OK. This is entirely based on the first step algorithm.
Ok, hint features can, then, is there any algorithm that has not been solved throughout the map? Yes, if you can't find a card, you can't find a card, then it is not enough! Remember all the logs of Hint, that is, the total can be connected.
At this point, the problem related to all algorithms is completed. The implementation of the second step algorithm is much larger, and the worst case should be approximately 50 times the amount of single connection algorithm calculation (related to the total number of cards and the position of the poster). The time of the secondary computation flower is too small, and it can be fully fluent in the actual operation. The above data is the theoretical value I estimate, because there is no problem in actual testing, I am too lazy to calculate the true relatively reliable meal. This part is also part I think can be improved. Open, I hope everyone can provide some better, more clever ways, I think I calculate the number of widths and how to solve the method is more stupid, almost The basic algorithm is fast, one is calculated. Is there a better way? I look forward to it, I will think about it again, too busy, too lazy, mainly lazy, I feel that I can use it.
I haven't written such a long time for a long time. In addition to the program, haha. Finally, I sincerely hope to help you. I also hope that Jzgenius users can find their own answers. I hope that everyone can propose the actual recommendations of criticism and improvement, let me improve.
