Triangle War
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 2685
Accepted: 1061
Description
Triangle War is a two-player game played on the following triangular grid:
Two players, A and B, take turns filling in any dotted line connecting two dots, with A starting first. Once a line is filled, it cannot be filled again. If the line filled by a player completes one or mZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcmUgdHJpYW5nbGVzLCBzaGUgb3ducyB0aGUgY29tcGxldGVkIHRyaWFuZ2xlcyBhbmQgc2hlCiBpcyBhd2FyZGVkIGFub3RoZXIgdHVybiAoaS5lLiB0aGUgb3Bwb25lbnQgc2tpcHMgYSB0dXJuKS4gVGhlIGdhbWUgZW5kcyBhZnRlciBhbGwgZG90dGVkIGxpbmVzIGFyZSBmaWxsZWQgaW4sIGFuZCB0aGUgcGxheWVyIHdpdGggdGhlIG1vc3QgdHJpYW5nbGVzIHdpbnMgdGhlIGdhbWUuIFRoZSBkaWZmZXJlbmNlIGluIHRoZSBudW1iZXIgb2YgdHJpYW5nbGVzIG93bmVkIGJ5IHRoZSB0d28gcGxheWVycyBpcyBub3QgaW1wb3J0YW50LiA8YnI+Cjxicj4KRm9yIGV4YW1wbGUsIGlmIEEgZmlsbHMgaW4gdGhlIGxpbmUgYmV0d2VlbiAyIGFuZCA1IGluIHRoZSBwYXJ0aWFsIGdhbWUgb24gdGhlIGxlZnQgYmVsb3c6IDxicj4KPGNlbnRlcj48aW1nIHNyYz0="http://www.2cto.com/uploadfile/Collfiles/20140627/20140627091500135.jpg" alt="\">
Then, she owns the triangle labelled A and takes another turn to fill in the line between 3 and 5. B can now own 3 triangles (if he wishes) by filling in the line between 2 and 3, then the one between 5 and 6, and finally the one between 6 and 9. B would then
make one more move before it is A"s turn again.
In this problem, you are given a number of moves that have already been made. From the partial game, you should determine which player will win assuming that each player plays a perfect game from that point on. That is, assume that each player always chooses
the play that leads to the best possible outcome for himself/herself.
Input
You will be given a number of games in the input. The first line of input is a positive integer indicating the number of games to follow. Each game starts with an integer 6 <= m <= 18 indicating the number of moves that have been made in the game. The next
m lines indicate the moves made by the two players in order, each of the form i j (with i < j) indicating that the line between i and j is filled in that move. You may assume that all given moves are legal.
Output
For each game, print the game number and the result on one line as shown below. If A wins, print the sentence "A wins." If B wins, print "B wins."
Sample Input
4
6
2 4
4 5
5 9
3 6
2 5
3 5
7
2 4
4 5
5 9
3 6
2 5
3 5
7 8
6
1 2
2 3
1 3
2 4
2 5
4 5
10
1 2
2 5
3 6
5 8
4 7
6 10
2 4
4 5
4 8
7 8
Sample Output
Game 1: B wins.
Game 2: A wins.
Game 3: A wins.
Game 4: B wins.
Source
East Central North America 1999
題意：
兩個人玩游戲，依次在三角形上放邊，如果能構成三角形，則獎勵繼續該此人放，問最後得到的三角形多。
思路：
給邊編號，記憶化搜索就行，做過好多這種題，就不多寫思路了。
代碼：
#include
#include
#include
#include
#include
#include
#include
