题目描述
小 A 和小 B 在下五子棋。
五子棋是在一个由网格构成的棋盘内进行的。
网格有 15 行 15 列,共有 225 个交叉点。
小 A 先手执黑棋,小 B 后手执白棋。
两人轮流下棋,每次下棋都将一个自己的棋子放在棋盘上一个空白的交叉点上。
然而,由于小 A 和小 B 都不知道五子棋的胜利条件,所以即使有一方已经胜利了,他们仍然会继续下棋。
现在想请你帮忙分析一下,所下的棋局是在第几步结束的。
当然,也有可能他们最终仍然没有分出胜负,这时请判定他们平局。
五子棋的胜利条件是这样的:当同一行或同一列或同一斜线(即与网格线成 45° 角的直线)上连续的五个或五个以上交叉点放有同色棋子的时候,立即判定使用该颜色棋子的玩家获得胜利,游戏结束。
模拟
对于每一个当前下的棋子,对其使用双指针进行横向、纵向、左斜、右斜扫描(8个while循环);
- 首先棋盘数组a[16][16]用0表示空、1表示A下的、2表示B下的;
- check时给出参数k,k=1代表这个棋子是A下的,k=2代表这个棋子是B下的;
- 根据1、2的设定就可以利用a[x][y]^k的值来判定这个位置是否存在A或B之前下的棋子;如果这个值为0,则意味着该位置存在当前落子人之前下的棋子,否则不存在,则该位置可能是空的也可能是对手下的棋子;
- 注意,==比^优先级高,因此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;
}