题目描述

小 A 和小 B 在下五子棋。

五子棋是在一个由网格构成的棋盘内进行的。

网格有 15 行 15 列，共有 225 个交叉点。

小 A 先手执黑棋，小 B 后手执白棋。

两人轮流下棋，每次下棋都将一个自己的棋子放在棋盘上一个空白的交叉点上。

然而，由于小 A 和小 B 都不知道五子棋的胜利条件，所以即使有一方已经胜利了，他们仍然会继续下棋。

现在想请你帮忙分析一下，所下的棋局是在第几步结束的。

当然，也有可能他们最终仍然没有分出胜负，这时请判定他们平局。

五子棋的胜利条件是这样的：当同一行或同一列或同一斜线（即与网格线成 45° 角的直线）上连续的五个或五个以上交叉点放有同色棋子的时候，立即判定使用该颜色棋子的玩家获得胜利，游戏结束。

模拟

对于每一个当前下的棋子，对其使用双指针进行横向、纵向、左斜、右斜扫描（8个while循环）；

1. 首先棋盘数组a[16][16]用0表示空、1表示A下的、2表示B下的；
2. check时给出参数k，k=1代表这个棋子是A下的，k=2代表这个棋子是B下的；
3. 根据1、2的设定就可以利用a[x][y]^k的值来判定这个位置是否存在A或B之前下的棋子；如果这个值为0，则意味着该位置存在当前落子人之前下的棋子，否则不存在，则该位置可能是空的也可能是对手下的棋子；
4. 注意，==比^优先级高，因此2^2==1的值为2而(2^2)==0的值为1，一定要注意这一点；

时间复杂度$O(n)$

对n个棋子进行判定，每个棋子的判定是O(1)，因为每个棋子虽然最多要走8个while循环，但是每个while循环最多5次，因此最多不过40次，仍是O(1)，所以总体时间复杂度就是O(n);

C++ 代码

#include <iostream>

using namespace std;

const int N=16;
int a[N][N];
int n;
//对于最新下的这一颗棋子，判定其是否和周围的棋子构成5个棋子的连线
//k=1代表A，k=2代表B
//a中元素1代表A的子，2代表B的子，0代表空
//则a[i][j]^k==0则代表当前位置有k的子
bool check(int x, int y, int k){
    //判断横着的棋子是否5个一线
    int l=x+1, r=x;
    //一下八个while语句我都忽略了^与==的优先级，如果不加括号会先算==得到0再进行^;就这里debug了好久；
    while(--l>0&&(a[l][y]^k)==0);
    while(++r<N&&(a[r][y]^k)==0);
    if(r-l-1>=5)
        return true;
    //判断竖着的
    l=y+1, r=y;
    while(--l>0&&(a[x][l]^k)==0);
    while(++r<N&&(a[x][r]^k)==0);
    if(r-l-1>=5)
        return true;
    //判断y=-x形的
    int l1=x+1, l2=y+1, r1=x, r2=y;
    while(--l1>0&&--l2>0&&(a[l1][l2]^k)==0);
    while(++r1<N&&++r2<N&&(a[r1][r2]^k)==0);
    if(r1-l1-1>=5)
        return true;
    //判断y=x形的
    l1=x-1, l2=y+1, r1=x, r2=y;
    while(++l1>0&&--l2<N&&(a[l1][l2]^k)==0);
    while(--r1<N&&++r2>0&&(a[r1][r2]^k)==0);
    if(l1-r1-1>=5)
        return true;
    return false;
}

int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int x, y;
        cin>>x>>y;
        if(i%2==0)
            a[x][y]=1;
        else
            a[x][y]=2;
        if(i%2==0&&check(x, y, 1)){
            printf("A %d", i+1);
            return 0;
        }
        else if(i%2!=0&&check(x, y, 2)){
            printf("B %d", i+1);
            return 0;
        }
    }
    printf("Tie");
    return 0;
}