Triangle War
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 3066 | Accepted: 1207 |
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 more triangles, she owns the completed triangles and she is awarded another turn (i.e. the opponent skips a turn). The game ends after all dotted lines are filled in, and the player with the most triangles wins the game. The difference in the number of triangles owned by the two players is not important.
A，
B两名玩家轮流连接一次图中带有数字的点之间的虚线（
A先手），每条虚线只能被连接一次，每当一名玩家将一个或多个三角形（指边长为一单位的最小三角形）的所有虚线全部连接时，他连成的三角形个数将计入他的总分，并且，他将被奖励一个回合（换言之对手跳过一次行动）。当所有的
18条虚线均被连接时游戏结束，得分高者获胜。
For example, if A fills in the line between 2 and 5 in the partial game on the left below:
For example, if A fills in the line between 2 and 5 in the partial game on the left below:
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.
例如图中（
4,5已被连接，图不太清楚），如果
A连接左图中
2和
5之间的虚线，那么他将获得
A三角形的
1分，并被奖励一次行动，假设
A继续连接
3，
5。那么轮到
B时他将可以获得
3个三角形的得分（如果他够聪明到去依次连接
2,3；
5,6；
6,9的话），而且
B还可以再行动一次。
在本题中，题目将输入若干条已经被连接的虚线，你需要判断在这些虚线被连接后轮到谁行动，并判断出在给出的局面，而且双方都足够聪明的情况下谁将获胜。
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.
输入的第一行为一个正整数
T，代表本个用例中有
T局游戏。
每局游戏开始时将输入一个整数m，代表有m条虚线已被连接（6 <= m <= 18）。
接下来的m行，每行将输入一个整数对（i , j）（保证i小于j）代表ij之间的虚线已被A或B连接，（游戏中A先手）。
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."
对每一局游戏，输出游戏局数和胜负结果（
A wins或
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.
先贴上参考的博文链接：
博弈（alpha-beta 剪枝）POJ —— 1085 Triangle War
poj 1085 Triangle War
我觉得这两篇博文写得已经比较完备了，我就直接贴上我的代码及注释吧，和朱杰大佬讨论了一上午，这题解法很巧，位运算的一些技巧真的要自己想实在太难了！
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;int StrMap[11][11] = { // 保存每个单位三角形代表的数字{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },{ 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0 },{ 0, 0, 0, 1, 3, 5, 0, 0, 0, 0, 0 },{ 0, 2, 1, 0, 0, 6, 8, 0, 0, 0, 0 },{ 0, 0, 3, 0, 0, 4, 0, 9, 11,0, 0 },{ 0, 0, 5, 6, 4, 0, 7, 0, 12,14,0 },{ 0, 0, 0, 8, 0, 7, 0, 0, 0, 15,17 },{ 0, 0, 0, 0, 9, 0, 0, 0, 10,0, 0 },{ 0, 0, 0, 0, 11,12,0, 10,0, 13, 0 },{ 0, 0, 0, 0, 0, 14,15,0, 13, 0, 16 },{ 0, 0, 0, 0, 0, 0, 17,0, 0, 16,0 },
};
int tri[9] = { 7, 56, 98, 448, 3584, 6160, 28672, 49280, 229376 };
int end_state = (1 << 18) - 1; // 所有边，即2^0+2^1+2^2+...+2^16+2^17=2^18-1int calc(int cur_state, int new_state)
{int cnt = 0;for (int i = 0; i < 9; i++)if ((cur_state&tri[i]) != tri[i] && (new_state &tri[i]) == tri[i])cnt++;//这个意思即旧图与边权取公共部分是没有的，而新图是有的，&的操作是有1为1，即可理解为取公共，因为cur_state和new_state‘包含’tri[i]（不好解释的样子。。。这个题的位操作实在太巧妙了！）return cnt;
}int alphabeta(int player, int cur_state, int alpha, int beta, int ca, int cb)
{if (ca >= 5)return 1;if (cb >= 5)return -1;int remain = (~cur_state)&end_state;while (remain) {int move = remain&(-remain);//你可以理解为可选的边已经按数值从大到小排好序，这个步骤就是取当前最大的数值边int tmp = calc(cur_state, cur_state | move);int ta = ca, tb = cb;player ? tb += tmp : ta += tmp;int v;if (tmp)v = alphabeta(player, cur_state | move, alpha, beta, ta, tb);else v = alphabeta(player ^ 1, cur_state | move, alpha, beta, ta, tb);player ? beta = min(beta, v) : alpha = max(alpha, v);if (beta <= alpha)break;remain -= move;}return player ? beta : alpha;
}int main()
{int T, w = 0,n;scanf("%d", &T);while (T--) {int cur_state = 0; // 当前局面int ca = 0; // A 的得分int cb = 0; // B 的得分int alpha = -1,beta = 1;int player = 0;scanf("%d", &n);for (int i = 0; i < n; i++) {int u, v;scanf("%d%d", &u, &v);int tmp = calc(cur_state, cur_state | 1 << StrMap[u][v]);player ? cb += tmp : ca += tmp;if (!tmp) player ^= 1;cur_state = cur_state | 1 << StrMap[u][v];}int ans = alphabeta(player, cur_state, alpha, beta, ca, cb);printf("Game %d: %c wins.\n", ++w, ans > 0 ? 'A' : 'B');}return 0;
}总而言之，这道题很有意思，有很多巧妙的技巧值得回味！