[刷题]算法竞赛入门经典(第2版) 4-3/UVa220

书上具体所有题目：http://pan.baidu.com/s/1hssH0KO
代码：（Accepted，0 ms）

//UVa 220 - Othello
#include<iostream>
char Board[11][11], Current, Command[5];
bool Flag, L_Refresh;//flag用于空格的输出,同时可以判断出本局是不是当前颜色的棋子无路可走
int Times, Num[2];//Num:0白1黑
int Rx[] = { 0, 0,1,-1,1,-1,1,-1 };
int Ry[] = { 1,-1,0, 0,1,-1,-1,1 };
inline char oppo() { return (Current == 'W' ? 'B' : 'W'); }

bool judge(int i, int j, int x, int y, bool is_print) {
    int ii = i + 1, jj = j + 1, flg = 0;
    while ((i += x) < 8 && (j += y) < 8 && i >= 0 && j>=0) {
        if (Board[i][j] == '-') break;
        if (Board[i][j] == Current) {
            if (!flg) break;
            if (is_print) {
                if (Flag) printf(" ");
                printf("(%d,%d)", ii, jj);
            }
            if (!Flag) Flag = true;
            return true;
        }
        ++flg;
    }
    return false;
}

void change(int i, int j, int x, int y) {
    int n = 0;
    while (Board[i += x][j += y] != Current) {
        Board[i][j] = Current, ++n;
    }
    Current == 'W' ? (Num[0] += n, Num[1] -= n) : (Num[0] -= n, Num[1] += n);
}

void L(bool is_print) {
    L_Refresh = 1, Flag = 0;
    for (int i = 0;i < 8;++i)  for (int j = 0;j < 8;++j) {
        if (Board[i][j] != '-') continue;
        for (int l = 0;l < 8;++l)
            if (judge(i, j, Rx[l], Ry[l], is_print))  break;
    }
    if (is_print) Flag ? printf("\n") : printf("No legal move.\n");
}

void M() {
    char i = Command[1] - 49, j = Command[2] - 49;
    if (!L_Refresh) L(0);
    if (!Flag) Current = oppo();
    for (int l = 0;l < 8;++l)
        if (judge(i, j, Rx[l], Ry[l], 0)) change(i, j, Rx[l], Ry[l]);
    Current == 'W' ? Num[0] += 1 : Num[1] += 1;
    Board[i][j] = Current;
    Current = oppo();
    L_Refresh = 0;
    printf("Black - %2d White - %2d\n", Num[1], Num[0]);
}

void Q() {
    for (int i = 0;i < 8;++i) printf("%s\n", Board[i]);
}

int main()
{
    //freopen("in.txt", "r", stdin);
    scanf("%d", &Times);
    while (Times--) {
        for (int i = 0;i < 8;++i) scanf("%s", Board[i]);
        scanf("\n%c", &Current);
        L_Refresh = 0;
        Num[0] = Num[1] = 0;
        for (int i = 0;i < 8;++i)  for (int j = 0;j < 8;++j) {
            if (Board[i][j] == 'W') ++Num[0];
            else if (Board[i][j] == 'B') ++Num[1];
        }
        while (scanf("%s", Command) && Command[0] != 'Q')
            Command[0] == 'L' ? L(1) : M();
        Q();
        if (Times) printf("\n");
    }
    return 0;
}

分析：
在uDebug上调试都对了，提交时还是无限WA，挠的头发都要掉光了，最后发现忘记把freopen(“in.txt”, “r”, stdin);加注释了@。@。。。。气得我笑出声。
首先是List all possible moves for the current player.有上下左右与4条斜线8种情况。8*8个格子每个都要检索一遍。先judge()查看每个位置各个方向是否legal，如果可以放置，输出之。输出直接放在judge里了，不高兴写入字符数组了，后面M()也会用到judge，这时不希望他输出，于是给judge()加了个is_print变量来控制。尽量代码重用。还有对于这八个方向，我一开始是用的傻傻的枚举，

if (judge(i, j, 0, 1, is_print)) continue;
if (judge(i, j, 0, -1, is_print)) continue;
if (judge(i, j, 1, 0, is_print)) continue;
if (judge(i, j, -1, 0, is_print)) continue;
if (judge(i, j, 1, 1, is_print)) continue;
if (judge(i, j, -1, -1, is_print)) continue;
if (judge(i, j, 1, -1, is_print)) continue;
if (judge(i, j, -1, 1, is_print)) continue;

后来VJ上看到别人用以下数组，

int rx[] = { 0, 0,1,-1,1,-1,1,-1 }， ry[] = { 1,-1,0, 0,1,-1,-1,1 };

一开始没看懂他这奇怪的数组干嘛的，看懂后真的是令我拍大腿叫绝。
所以现在只需一个循环

for (int l = 0;l < 8;++l)
        if (judge(i, j, Rx[l], Ry[l], 0)) change(i, j, Rx[l], Ry[l]);

即可，真心方便。下面M()函数也一样。
还有就是L_Refresh的作用。系统有可能一口气执行多次L()（当然我不确定，只是有可能），也可能未执行就执行M，这时需要知道是不是无合法操作，还得先执行L()，L_Refresh就是用来检测L()有没有执行过，且防止其重复执行多次。
还有那个输出，比如“Black - 1 White - 4”，数字1和4在输出时应用“ %2d”输出，而不是两个空格键。之前看题目“Black - xx White - yy”的xx、yy没看懂，后来才知道是占两个格子的意思。

[刷题]算法竞赛入门经典(第2版) 4-3/UVa220 - Othello

推荐阅读