题解：P6050 [RC-02] 游戏

Hero_Broom · 2024-10-27 14:38:24 · 题解

Perhaps a better reading experience?

~~刷大模拟的时候碰巧看到这一篇小模拟，大模拟调不出来，于是做小模拟来涨自信~~

题目大意

题目链接

让你模拟一场游戏的进行，规则在题目里说得很清楚了。

题解

这道题可以分为几个部分：输入输出、判断输入数据是否合法，吃掉对方的棋子，最后就是判断游戏是否结束。我们可以一步一步地解决

\texttt{I.} 移动棋子和判定数据是否合法

在题目中，数据有可能出现下面几种不合法的情况：

数据超出范围，这一点是很好判断的；
目标点上已有其它棋子存在；
起始点上没有棋子或是有对方的棋子。

这个部分是比较简单的。对于第三条，我们使用一个变量 now 记录当前移动的棋子。

那么我们就可以写出判断数据是否合法的 command_correct 函数。

inline bool in_range(int t){return (t>=1&&t<=n);}
inline bool command_correct(){
    if(!in_range(sx)||!in_range(sy)||!in_range(ex)||!in_range(ey)) return 0;
    if(board[sx][sy]!=now||board[ex][ey]!=0) return 0;
    return 1;
}

代码中，sx 和 sy 代表起始点坐标，ex 和 ey 代表目标点坐标，board 数组是棋盘。

注意在读如数据的时候我们要交换输入的 x 坐标和 y 坐标，因为在 C++ 中，a[i][j] 表示第 i 行第 j 列，而数据中给出的是第 i 列第 j 行。

scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
swap(sx,sy),swap(ex,ey);
if(!command_correct()){
    printf("0\n");
    return 0;
}

\texttt{II.} 吃对方的棋子

在判断是否可以吃掉对方棋子时，我们只需要判断当前输入的目标点所在的行和列是否存在可以吃棋的情况，而不需要每次输入把整个棋盘遍历一遍。

有一个需要注意的点在题目中说了：敌方棋子全部相邻，并且我方有一颗棋子与敌方相邻，而且此局面为我方主动走成，则我方可以把这一列上敌方的棋子全部吃掉。也就是说，我们在判断的时候要判断当前局面是否为我方主动形成的，否则就不能判定为吃棋。

首先我们要先统计出当前行的我方和对方的棋子数量，如果棋子的数量不对，那么就直接返回就可以了。

我们要在每一次循环之后更新 now 的值。我们把红色一方设为 1，蓝色设为 2。

当我们需要统计己方的棋子数时，只要 cnta+=(board[ex][i]==now) 即可，而要表示对方棋子，我们可以使用 3-now 来表示，所以统计对方棋子数时我们可以 cntb+=(board[ex][i]==3-now)。在这里，cnta 和 cntb 分别表示己方的棋子数和对方的棋子数。

这里的代码以行为例，列的代码也差不多。

cnta=cntb=tot=0;
for(int i=1;i<=n;i++){
    tot+=(board[ex][i]!=0);
    cnta+=(board[ex][i]==now);
    cntb+=(board[ex][i]==3-now);
}
if(!(tot==n-1||(n>4&&tot==n-2))) return;
if(!(cnta==n-2||(n>4&&cnta==n-3))) return;
if(!((cntb==1)||(n>4&&cntb==2))) return;

接下来判断棋子的位置是否正确。

在判断棋子位置时，我们需要判断一下几种情况：

每一方的棋子必须相邻；
己方必须有一个棋子与对方相邻。

这里第二点需要注意，一开始我在做时就是因为这个 WA 了。

ca=cb=tmp=0;
for(int i=1;i<=n;i++){
    if(board[ex][i+1]==3-board[ex][i]) tmp=1;
    if(board[ex][i]!=now){
        if(ca!=0&&ca!=cnta) return;
        ca=0;
    }else ca++;
    if(board[ex][i]!=3-now){
        if(cb!=0&&cb!=cntb) return;
        cb=0;
    }else cb++;
}
if(tmp==0) return;

ca 和 cb 表示两方相邻的棋子数，tmp 表示是否满足上面的第二种情况。

最后如果上面的条件都满足，那么就可以吃棋子了。

for(int i=1;i<=n;i++)
    if(board[ex][i]==3-now) board[ex][i]=0;

以上是模拟一行中吃子的代码，而列也是一样的，只要把所有的 board[ex][i] 改成 board[i][ey] 即可。

下面是列的代码：

void eat_col(){
    cnta=cntb=tot=0;
    for(int i=1;i<=n;i++){
        tot+=(board[i][ey]!=0);
        cnta+=(board[i][ey]==now);
        cntb+=(board[i][ey]==3-now);
    }
    if(!(tot==n-1||(n>4&&tot==n-2))) return;
    if(!(cnta==n-2||(n>4&&cnta==n-3))) return;
    if(!((cntb==1)||(n>4&&cntb==2))) return;
    ca=cb=tmp=0;
    for(int i=1;i<=n;i++){
        if(board[i+1][ey]==3-board[i][ey]){
            tmp=1;
        }
        if(board[i][ey]!=now){
            if(ca!=0&&ca!=cnta) return;
            ca=0;
        }else ca++;
        if(board[i][ey]!=3-now){
            if(cb!=0&&cb!=cntb) return;
            cb=0;
        }else cb++;
    }
    if(tmp!=0){
        for(int i=1;i<=n;i++)
            if(board[i][ey]==3-now) board[i][ey]=0;
    }
}

\texttt{III.} 判断输赢

这一个部分就比较简单了。有一方赢应该满足下面任选一个条件：

对方棋子少于 \frac{N}{2} 个；
对方无棋可走。

这个部分比较简单，就直接贴代码了。

inline bool in_range(int t){return (t>=1&&t<=n);}
inline bool can_move(int x,int y){
    if(in_range(x-1)&&in_range(y)&&board[x-1][y]==0) return 1;
    if(in_range(x+1)&&in_range(y)&&board[x+1][y]==0) return 1;
    if(in_range(x)&&in_range(y+1)&&board[x][y+1]==0) return 1;
    if(in_range(x)&&in_range(y-1)&&board[x][y-1]==0) return 1;
    return 0;
}
short is_win(){
    bool rflag=0,bflag=0;
    red_tot=blue_tot=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(board[i][j]==1){
                red_tot++;
                if(can_move(i,j)) rflag=1;
            }
            if(board[i][j]==2){
                blue_tot++;
                if(can_move(i,j)) bflag=1;
            }
//          red_tot+=(board[i][j]==1);
//          blue_tot+=(board[i][j]==2);
        }
    if(!rflag) return 2;
    if(!bflag) return 1;
    if(red_tot<=n/2) return 2;
    if(blue_tot<=n/2) return 1;
    return 0;
}

\texttt{IV.} 初始化

这个部分也比较简单，按照题意模拟即可。

inline void init(){
    for(int i=1;i<=n/2;i++) board[1][i]=board[n][i]=1;
    for(int i=n/2+1;i<=n;i++) board[1][i]=board[n][i]=2;
    for(int i=2;i<=n-1;i++) board[i][1]=1,board[i][n]=2;
}

\texttt{V.} 主函数

在写主函数时，只需要注意输入的时候将横纵坐标交换一下就可以了，因为输入中是先输入列再输入行。

int main(){
    scanf("%d%d",&n,&m);
    init();
    while(m--){
        scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
        swap(sx,sy),swap(ex,ey);
        if(!command_correct()){
            printf("0\n");
            return 0;
        }
        move();
        eat();
        now=(now==1?2:1);
        if(is_win()==0) continue;
        printf("2\n%s\n",is_win()==1?"red":"blue");
        out();
        return 0;
    }
    printf("1\n");
    out();
    return 0;
}

\texttt{VI.} 易错点

输入的时候将横纵坐标交换一下；
判断输赢时应该判断是否有一方无棋可走，如果没有判断会 WA 几个点；
在判断是否可以吃掉对方的棋子时，两方需有一个旗子相邻，这点也要考虑到。

代码

还是一道比较简单的小模拟，代码 150 行都没到，是一道不错的锻炼码力的题目。

上面说的自认为已经是比较清楚的了，代码没有注释，如果看不懂的可以往前看一看解释，这样才能锻炼思维。

#include<bits/stdc++.h>
using namespace std;
int n,m;
int sx,sy,ex,ey;
int red_tot,blue_tot;
int tot,cnta,cntb,ca,cb;
bool tmp;
short board[20][20],now=1;//0:empty 1:red   2:blue
inline void init(){
    for(int i=1;i<=n/2;i++) board[1][i]=board[n][i]=1;
    for(int i=n/2+1;i<=n;i++) board[1][i]=board[n][i]=2;
    for(int i=2;i<=n-1;i++) board[i][1]=1,board[i][n]=2;
}
inline bool in_range(int t){return (t>=1&&t<=n);}
inline bool command_correct(){
    if(!in_range(sx)||!in_range(sy)||!in_range(ex)||!in_range(ey)) return 0;
    if(board[sx][sy]!=now||board[ex][ey]!=0) return 0;
    return 1;
}
inline void move(){swap(board[sx][sy],board[ex][ey]);}
void eat_line(){
    cnta=cntb=tot=0;
    for(int i=1;i<=n;i++){
        tot+=(board[ex][i]!=0);
        cnta+=(board[ex][i]==now);
        cntb+=(board[ex][i]==3-now);
    }
    if(!(tot==n-1||(n>4&&tot==n-2))) return;
    if(!(cnta==n-2||(n>4&&cnta==n-3))) return;
    if(!((cntb==1)||(n>4&&cntb==2))) return;
    ca=cb=tmp=0;
    for(int i=1;i<=n;i++){
        if(board[ex][i+1]==3-board[ex][i]) tmp=1;
        if(board[ex][i]!=now){
            if(ca!=0&&ca!=cnta) return;
            ca=0;
        }else ca++;
        if(board[ex][i]!=3-now){
            if(cb!=0&&cb!=cntb) return;
            cb=0;
        }else cb++;
    }
    if(tmp!=0){
        for(int i=1;i<=n;i++)
            if(board[ex][i]==3-now) board[ex][i]=0;
    }
}
void eat_col(){
    cnta=cntb=tot=0;
    for(int i=1;i<=n;i++){
        tot+=(board[i][ey]!=0);
        cnta+=(board[i][ey]==now);
        cntb+=(board[i][ey]==3-now);
    }
    if(!(tot==n-1||(n>4&&tot==n-2))) return;
    if(!(cnta==n-2||(n>4&&cnta==n-3))) return;
    if(!((cntb==1)||(n>4&&cntb==2))) return;
    ca=cb=tmp=0;
    for(int i=1;i<=n;i++){
        if(board[i+1][ey]==3-board[i][ey]){
            tmp=1;
        }
        if(board[i][ey]!=now){
            if(ca!=0&&ca!=cnta) return;
            ca=0;
        }else ca++;
        if(board[i][ey]!=3-now){
            if(cb!=0&&cb!=cntb) return;
            cb=0;
        }else cb++;
    }
    if(tmp!=0){
        for(int i=1;i<=n;i++)
            if(board[i][ey]==3-now) board[i][ey]=0;
    }
}
inline void eat(){
    eat_line();
    eat_col();
}
inline bool can_move(int x,int y){
    if(in_range(x-1)&&in_range(y)&&board[x-1][y]==0) return 1;
    if(in_range(x+1)&&in_range(y)&&board[x+1][y]==0) return 1;
    if(in_range(x)&&in_range(y+1)&&board[x][y+1]==0) return 1;
    if(in_range(x)&&in_range(y-1)&&board[x][y-1]==0) return 1;
    return 0;
}
short is_win(){
    bool rflag=0,bflag=0;
    red_tot=blue_tot=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++){
            if(board[i][j]==1){
                red_tot++;
                if(can_move(i,j)) rflag=1;
            }
            if(board[i][j]==2){
                blue_tot++;
                if(can_move(i,j)) bflag=1;
            }
        }
    if(!rflag) return 2;
    if(!bflag) return 1;
    if(red_tot<=n/2) return 2;
    if(blue_tot<=n/2) return 1;
    return 0;
}
inline void out(){
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) printf("%c",board[i][j]==0?'.':board[i][j]==1?'h':'l');
        printf("\n");
    }
}
int main(){
    scanf("%d%d",&n,&m);
    init();
    while(m--){
        scanf("%d%d%d%d",&sx,&sy,&ex,&ey);
        swap(sx,sy),swap(ex,ey);
        if(!command_correct()){
            printf("0\n");
            return 0;
        }
        move();
        eat();
        now=(now==1?2:1);
        if(is_win()==0) continue;
        printf("2\n%s\n",is_win()==1?"red":"blue");
        out();
        return 0;
    }
    printf("1\n");
    out();
    return 0;
}