HDU 3683_综合

因为少了一句if，这个AC迟来了一年...
解法：假设A先手，B后手。
    1.如果A有必胜点，放下去即连成5个，那么A一步获胜。
    2.如果B有两个以上的必胜点，那么B两步必胜。
    3.如果B只有一个必胜点，那么A第一步肯定放在B的必胜点上。再判断A是否有两个以上的必胜点，如果有，A三步获胜。
    4.枚举A第一步的走法，如果能走出两个以上的必胜点，那么A三步获胜。
    5.如果以上情况都不成立，那三步之内没人可以获胜。

#include <iostream>
using namespace std;struct POINT
{int x, y;
};int n, white, black;
int player, other;
int map[15][15];
int dir[4][2] = {
   {0, 1}, {1, 0}, {1, 1}, {1, -1}};
char str[][10] = {"", "white", "black"};bool ReadCase()
{int i, col;POINT tmp;scanf("%d", &n);if (n == 0){return false;}memset(map, 0, sizeof(map));white = black = 0;for (i = 0; i < n; i++){scanf("%d %d %d", &tmp.x, &tmp.y, &col);if (col == 0){white++;map[tmp.x][tmp.y] = 1;}else{black++;map[tmp.x][tmp.y] = 2;}}return true;
}bool Check()
{if (black == white){player = 2;other = 1;}else if (black == white + 1){player = 1;other = 2;}else{return false;}return true;
}bool Bound(POINT p)
{return p.x >= 0 && p.x <= 14 && p.y >= 0 && p.y <= 14;
}int GetMaxLength(POINT p, int c)
{int res = 0;for (int i = 0; i < 4; i++){int len = 0;POINT tmp = p;while (true){tmp.x = tmp.x + dir[i][0];tmp.y = tmp.y + dir[i][1];if (!Bound(tmp) || map[tmp.x][tmp.y] != c){break;}len++;}tmp = p;while (true){tmp.x = tmp.x - dir[i][0];tmp.y = tmp.y - dir[i][1];if (!Bound(tmp) || map[tmp.x][tmp.y] != c){break;}len++;}len++;if (len > res){res = len;}}return res;
}int GetWinPoint(POINT &p, int c)
{int num = 0;for (int i = 0; i < 15; i++){for (int j = 0; j < 15; j++){POINT tmp;tmp.x = i;tmp.y = j;int a = 0;if (map[tmp.x][tmp.y] == 0 && (a = GetMaxLength(tmp, c)) >= 5){num++;if (num == 1){p = tmp;}}//cout << a << endl;}}return num;
}void Solve()
{if (!Check()){printf("Invalid.\n");return;}POINT p, p2;int num;if (GetWinPoint(p, player) >= 1){printf("Place %s at (%d,%d) to win in 1 move.\n", str[player], p.x, p.y);return;}if ((num = GetWinPoint(p, other)) >= 2){printf("Lose in 2 moves.\n");return;}if (num == 1){map[p.x][p.y] = player;if (GetWinPoint(p2, player) >= 2){printf("Place %s at (%d,%d) to win in 3 moves.\n", str[player], p.x, p.y);return;}}else{for (int i = 0; i < 15; i++){for (int j = 0; j < 15; j++){if (map[i][j] == 0)
{map[i][j] = player;if (GetWinPoint(p2, player) >= 2){printf("Place %s at (%d,%d) to win in 3 moves.\n", str[player], i, j);return;}map[i][j] = 0;}}}}printf("Cannot win in 3 moves.\n");
}int main()
{while (ReadCase()){Solve();}return 0;
}