企业官网建设流程全解析

对弈

时间限制：1秒 空间限制：256M

知识点：枚举

网页链接

牛客tracker

牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！

题目描述

善弈者谋势，不善弈者谋子。

​ ——《弈林新编》

蒟蒻H t B e s t HtBestHtBest与神犇W H Z WHZWHZ下棋（五子棋），H t B e s t HtBestHtBest执黑棋，W H Z WHZWHZ执白棋。由于H t B e s t HtBestHtBest天资愚笨，不会判断输赢，所以需要你帮他开发一个判断五子棋输赢的程序。

输入描述：

第一行有2 22个正整数n ， m n，mn，m，分别表示棋盘大小（ n ） （n）（n）和对弈步数。
接下来m mm行，每行两个正整数x i , y i x_i,y_ixi​,yi​，表示对弈者下棋的坐标，第2 、 4 、 6 … 2、4、6…2、4、6…行是HtBest下的棋子，第3 、 5 、 7 … 3、5、7…3、5、7…行是W H Z WHZWHZ下的棋子。

输出描述：

第一行一个字符串s ss和一个正整数n u m numnum，用空格隔开，分别表示对弈的胜负结果和该结果出现时的步数，如果H t B e s t HtBestHtBest胜则s = “ H t B e s t ” s=“HtBest”s=“HtBest”，n u m numnum为H t B e s t HtBestHtBest胜利时的步数（为偶数），如果W H Z WHZWHZ胜则s = “ W H Z ” s=“WHZ”s=“WHZ”，n u m numnum为W H Z WHZWHZ胜利时的步数（为奇数），如果对弈m mm步后胜负仍未定，则s = “ U N K ” s=“UNK”s=“UNK”，n u m = m num=mnum=m。
提示：当棋盘上第一次有五个子连续排列（横竖斜都可）时，胜负已定。在这之后，两人有可能仍继续落子。

示例1

输入：

10 20 1 1 1 2 2 1 2 2 3 1 3 2 4 1 4 2 5 1 5 2 6 1 6 2 7 1 7 2 8 1 8 2 9 1 9 2 10 1 10 2

输出：

HtBest 9

说明：

在第9 99步时，H t B e s t HtBestHtBest获胜，当前局面：

示例2

输入：

10 27 8 6 9 4 2 1 7 5 4 7 8 4 4 3 5 4 10 3 5 5 9 7 9 5 3 4 6 3 5 10 1 5 9 2 6 5 5 7 1 4 2 5 8 5 1 3 3 2 8 3 2 6

输出：

WHZ 22

说明：

在第2 22步时，W H Z WHZWHZ获胜，当前局面：

示例3

输入：

10 1 1 1

输出：

UNK 1

说明：

下一手后，胜负未分。

备注：

对于100 % 100\%100%的测试数据：
1 ≤ n ≤ 1000 1 ≤ n ≤ 10001≤n≤1000
1 ≤ m ≤ 100000 1 ≤ m ≤ 1000001≤m≤100000

解题思路

本题是模拟落子 + 定向胜负检测的经典五子棋判赢问题，利用「仅新落子可能形成五连」的性质，将每次胜负判定的复杂度从全盘扫描的O ( n 2 ) O(n^2)O(n2)优化为常数级，完美适配十万步的大规模数据。

1. 核心优化：仅检查当前落子点

五子棋中，只有刚刚落下的棋子才可能促成新的五连，此前的棋盘状态已经验证过无五连。因此每次落子后，只需以该棋子为中心，向四个方向延伸检查连续同色棋子数即可，无需全盘扫描，单次检查为O ( 1 ) O(1)O(1)常数开销。

2. 四个检测方向

五连共有四种形态：横向、纵向、主对角线（左上-右下）、副对角线（右上-左下）。对应四个方向向量：

• 纵向：行变化，列不变(1, 0)
• 横向：列变化，行不变(0, 1)
• 主对角线：行列同步增减(1, 1)
• 副对角线：行增列减(-1, 1)

对每个方向，以落子点为中心向两端各延伸最多4格，统计连续同色棋子的最大长度，若任意方向长度≥5，则当前玩家获胜。

3. 边界简化处理

由于最多仅需向四周延伸4格，因此给棋盘坐标整体加上偏移量（代码中为+3），让所有合法落子点周围都留有足够的缓冲区域，无需额外判断数组越界，大幅简化代码逻辑。

4. 整体流程

1. 初始化棋盘，所有位置标记为空。
2. 按顺序模拟每一步落子：奇数步（第1、3、5…步）为HtBest的黑棋，偶数步为WHZ的白棋。
3. 每落一子立即执行胜负检测，若形成五连，直接输出胜者与当前步数，终止程序。
4. 若所有m步走完仍未分出胜负，输出UNK与总步数m。

算法总时间复杂度为O ( m ) O(m)O(m)，可轻松处理十万步的输入规模。

总结

核心逻辑：利用五连必然包含最新落子的性质，将胜负检测限定在当前点的四个方向上，线性模拟每一步落子，首次检测到五连立即输出结果。
关键操作：定向四方向连续计数、坐标偏移简化边界处理、落子即检查提前终止。
效率保障：每次检查为常数级操作，总复杂度线性，十万步数据可毫秒级完成。

代码简要说明

1. 棋盘存储：使用vector<string>存储棋盘，大小设为n+8，初始值填充为-1代表空位；通过坐标整体+3的偏移，避免边界越界判断。
2. check检测函数：
   • 遍历四个方向向量，每个方向以落子点为中心，从-4到+4依次检查位置。
   • 统计连续同色棋子数，若计数达到5则立即返回true，表示获胜。
3. 落子主循环：
   • 按步循环读取坐标，通过i&1判断当前玩家：0对应HtBest，1对应WHZ。
   • 写入棋子后调用check函数，若获胜则按规则输出玩家名称与第i+1步的步数，直接返回结束程序。
4. 未分胜负处理：所有步数走完仍未触发胜利，输出UNK与总步数m。
5. 输入优化：关闭流同步并解绑tie，大幅提升十万级数据的读取速度。

代码内容

#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;ll n,m;vector<string>g;boolcheck(ll x,ll y,chart){for(constauto&[dx,dy]:{make_pair(1,0),make_pair(0,1),make_pair(1,1),make_pair(-1,1)}){ll c=0;for(ll i=-4;i<5;i++){if(g[x+i*dx][y+i*dy]==t){c++;if(c==5)returntrue;continue;}c=0;}}returnfalse;}voidsolve(){cin>>n>>m;g.assign(n+8,string(n+8,(char)-1));for(ll i=0;i<m;i++){ll x,y;cin>>x>>y;chart=i&1;x+=3;y+=3;g[x][y]=t;if(check(x,y,t)){if(t)cout<<"WHZ "<<i+1<<endl;elsecout<<"HtBest "<<i+1<<endl;return;}}cout<<"UNK "<<m<<endl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);solve();return0;}