题解 SP2128 【KROW - K-In-A-Row】

Mars_Dingdang · 2020-08-12 11:07:58 · 题解

这道题我调了好久总算 AC 了！不过居然只有一篇题解，因此我再来发一篇。其实这题就是暴力枚举，找 k 个连续的棋子。

题目大意

现在有一个 n\times m 的棋盘（m 行 n 列），里面 x 表示小 A 的棋子，o 表示小 B 的棋子，. 表示该处未落子。任意一方有连续的 k 颗棋子即获胜。简单地说，两人就是在 n\times m 的棋盘里下 k 子棋。一共有 t 组数据，要求输出两方的比分。（样例中的 file: 请自行忽略。）

大体思路

获胜条件：

首先思考一下：什么时候有人获胜？显然是当有 k 颗棋子连在一起时。因此需要分四种情况讨论：横、竖、两条对角线（斜）。若 k>\max(m,n)，显然无法连线，直接跳过。

变量声明

• 为了记录盘面，需要一个二位字符串保存。

• 同时需要两个变量 \textit{wina,winb} 记录连续的棋子数，在特定的时候需要归零（等会分析）；

• 以及一个标记变量 \textit{find} 表示是否已经找到，每组数据清零。

• 最后是两个变量 \textit{score\_a,score\_b}，用于记录两位选手的得分，初始化为零。

输入

这一部分就不再赘述，注意题目是输入 n,m，表示的是 m 行 n 列。代码如下：

    int t,n,m,k;//如题
    cin>>t;//数据组数
    for(int ppp=1;ppp<=t;ppp++){//共t组数据
            wina=winb=0;//将连续棋子数归零
        bool find=0;//标记变量初始化
        memset(a,0,sizeof(a));//清空盘面
        cin>>n>>m>>k;//输入（如题）
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                cin>>a[i][j];//输入盘面
            }
        }
        //未完待续……

横排连续 & 竖排连续

我之所以将这两个放在一起，是因为他们几乎一模一样。首先来看横排：遍历盘面，保持行不变（即外层循环为行，内层循环为列），然后判断每个棋子。

• 若该棋子为 x，则 wina+1，同时由于小 B 的棋子此时肯定已经不是连续的（除非已经大于等于 k 了），因此将其归零（若已达到 k 则不归零）。

• 同理，若该棋子为 o，则 winb+1，同时由于小 A 的棋子此时肯定已经不是连续的（除非已经大于等于 k 了），因此将其归零（若已达到 k 则不归零）。

• 如果遇到 .，表明此时双方棋子都断了，将两个变量都归零（若已达到 k 则不归零）。

竖排只须更改内外层循环即可（即外层循环为列，内层循环为行）。

代码如下：

    int tem=max(m,n);
    if(k>tem) continue;//无法连线，跳过
    for(int i=1;i<=m;i++){//横排
        for(int j=1;j<=n;j++){
            if(a[i][j]=='x'){//遇到棋子x
                wina+=1;//小A连续棋子数+1
                if(winb<k) winb=0;//未达到k则归零
            }
            else if(a[i][j]=='o'){//遇到棋子o
                winb+=1;//小B连续棋子数+1
                if(wina<k) wina=0;//未达到k则归零
            }
            else {//其他（棋子为‘.’）
                if(wina<k) wina=0;
                if(winb<k) winb=0;//归零
            }
        }
        if(wina>=k) {//若小A连续棋子数达到k
            score_a++;//得分+1
            find=1;//标记为已找到
            break;//横排结束循环
        }
        else if(winb>=k) {
            score_b++;
            find=1;
            break;
        }//同上
        wina=0,winb=0;//将连续棋子数初始化为0
    }
    wina=0,winb=0;
    if(find==1) continue;//若以找到则直接跳过
        for(int j=1;j<=n;j++){
            for(int i=1;i<=m;i++){//竖排
                if(a[i][j]=='x'){
                    wina+=1;
                    if(winb<k) winb=0;
                }
                else if(a[i][j]=='o'){
                    winb+=1;
                    if(wina<k) wina=0;
                }
                else {
                    if(wina<k) wina=0;
                    if(winb<k) winb=0;
                }
            }
            if(wina>=k) {
                score_a++;
                find=1;
                break;
            }
            else if(winb>=k) {
                score_b++;
                find=1;
                break;
            }
            wina=0,winb=0;
        }
        wina=0,winb=0;
        if(find==1) continue;//同上

斜排连续

这时候要分类讨论：是 / 还是 \。同时还需注意：有可能是

x....         
.x...
..x..
...x.
.....

也可能是

.....
.x...
..x..
...x.
....x

因此，左上角或右上角的位置是不确定的，需要两个循环嵌套。循环中判断内容大体同上。代码如下：

//第一种 ‘\’
for(int l=1;l<=n&&find==0;l++){
//在未找到的前提下遍历起点
    for(int ll=1;ll<=m&&find==0;ll++){
        wina=winb=0;//归零
        for(int i=ll,j=l;i<=m&&j<=n;i++,j++){
        //模拟一斜排
            if(a[i][j]=='x'){
                wina+=1;
                if(winb<k)winb=0;
            }
            else if(a[i][j]=='o'){
                winb+=1;
                if(wina<k)wina=0;
            }
            else {
                if(wina<k) wina=0;
                if(winb<k) winb=0;
            }//同前一部分
        }
        if(wina>=k) {//连续棋子数满足
            score_a++;//得分+1
            find=1;//标记为已找到
        break;//结束循环
        }
        else if(winb>=k) {
            score_b++;
            find=1;
        break;
        }//同上
        }
        }
        wina=0,winb=0;//归零
        if(find==1) continue;//找到则跳过
        //第二种：‘/'
        for(int l=1;l<=n&&find==0;l++){
        for(int lk=m;lk>=1&&find==0;lk--){
        //遍历起点
        for(int i=lk,j=l;i>=1&&j<=n;i--,j++){
        //模拟一斜排
            if(a[i][j]=='x'){
                wina+=1;
                if(winb<k)winb=0;
            }
            else if(a[i][j]=='o'){
                winb+=1;
                if(wina<k)wina=0;
            }
            else {
                    if(wina<k) wina=0;
                    if(winb<k) winb=0;
                }
        }
        if(wina>=k) {
            score_a++;
            find=1;
            break;
        }
        else if(winb>=k) {
            score_b++;
            find=1;
            break;
        }
        wina=0,winb=0;
        }
        }
        wina=winb=0;
        if(find==1) continue;//同上

最后再输出两人得分即可。

这种暴力枚举，时间复杂度最差是 O(t\times m\times n\times k)，事实证明不会超时，当然里面有些也可以优化。

（WoW，两百多行了qaq）