LG5380 [THUPC2019]鸭棋

发布于 2020-05-13  3.27k 次阅读

题面

黑色大模拟一题，身为大模拟爱好者的我当然要A掉它并且写一篇题解。

刚进来的同学切勿被黑色的难度给吓出去

切入正题

题意

题目中给出了一种很像象棋的棋叫做鸭棋的，具体告诉了你鸭棋的玩法。然后题目告诉你红蓝双方在棋盘上对弈的操作情况，让你模拟棋局，输出一些题目中需要的信息。

总的来说，一共有七种棋子，他们各有不同的走法，除走法外其他操作几乎与象棋相同。题目中除了移动操作，你还需要关注的是1.是否出现将军局面，2.对局是否结束（即棋盘上有没有王死去）。

我们结合代码片段进行余下的分析和解释。

代码

（共8.89KB）

其实在模拟类题目中不算特别长，因为其中大部分代码都没有大的思维量，并且语法十分简易毫无难度，不必担心。

我们分析题目中所有需要你做的操作。

  1. 判断移动是否合法
  2. 判断当前是否形成将军局面
  3. 游戏是否结束

如果我们使用了7个函数来分别解决7种棋子的移动判断，那么首先第1条被解决。接着我们判断落点处是否是对方的王，如果是则对局结束，所以第3条被解决。而我们发现，如果我们在移动后对棋盘上所有的棋子进行判断，判断其能否移动到对方的王上，只要所有棋子中有一颗能够攻击到对方的王，则此时形成将军局面，第2条被解决。

7个函数

这里是7种棋子的移动函数，表示我们试图将棋子（与函数种类匹配）从$(start_x,start_y)$移动到$(end_x,end_y)$，返回的bool值表示移动能否进行。

我们观察到题面上用了数学的方法来表示棋子的移动方法，于是我们同样以数学的方法解决棋子的移动。

初始化部分

enum chess //棋子种类
{
    NA,       //无（这个位置是空的）
    captain,  //王
    guard,    //士
    elephant, //象
    horse,    //马
    car,      //车
    duck,     //鸭
    soldier   //兵
};
enum belong_type //记录每颗棋子属于何方的类型
{
    RED,  //属于红方
    BLUE, //属于蓝方
    NOT   //不属于任何一方（即没有棋子）
};

const int walk_set[2] = {1, -1};               //移动中会使用到的集合
const string rank_string[2] = {"red", "blue"}; //输出棋子属于哪方时会用到的
const string chess_string[8] = {"NA", "captain", "guard", "elephant", "horse", "car", "duck", "soldier"};
//输出棋子名称时会用到的

chess board[10][9];             //棋盘，每一位上保存这一位的棋子种类
belong_type belong[10][9];      //保存棋盘上每一位上的棋子属于哪方
bool CHECK_MATE, GAME_OVER;     //将军局面，和游戏是否结束
int CAPTAIN_X[2], CAPTAIN_Y[2]; //存放双方的王的坐标

王（captain） 的移动

题面中说明王的可达的位置为$(x\pm1,y)$和$(x,y\pm1)$。

第一个for解决$(x\pm1,y)$，第二个for解决$(x,y\pm1)$。

同时如果移动成功，因为棋子是王，所以我们需要记录。

bool captian_move(int start_x, int start_y, int end_x, int end_y)
{
    for (int x = 0; x < 2; x++)
    {
        int to_x = start_x + walk_set[x], to_y = start_y;
        if (end_x == to_x && end_y == to_y)
        {
            CAPTAIN_X[belong[start_x][start_y]] = end_x;
            CAPTAIN_Y[belong[start_x][start_y]] = end_y;
            return true;
        }
    }
    for (int y = 0; y < 2; y++)
    {
        int to_x = start_x, to_y = start_y + walk_set[y];
        if (end_x == to_x && end_y == to_y)
        {
            CAPTAIN_X[belong[start_x][start_y]] = end_x;
            CAPTAIN_Y[belong[start_x][start_y]] = end_y;
            return true;
        }
    }
    return false;
}

士（guard） 的移动

士的可达的位置为$(x\pm1,y\pm1)$和$(x\pm1,y\mp1)$。

第一个for解决$(x\pm1,y\pm1)$，第二个for解决$(x\pm1,y\mp1)$。

bool guard_move(int start_x, int start_y, int end_x, int end_y)
{
    for (int x = 0; x < 2; x++)
    {
        int to_x = start_x + walk_set[x], to_y = start_y + walk_set[x];
        if (end_x == to_x && end_y == to_y)
            return true;
    }
    for (int x = 0; x < 2; x++)
    {
        int to_x = start_x + walk_set[x], to_y = start_y + walk_set[!x];
        if (end_x == to_x && end_y == to_y)
            return true;
    }
    return false;
}

象（elephant） 的移动

题面中是这样写的

可达的位置至多4个，对于任意$s_x,s_y∈{1,-1}$，分别有：
- 如果位置$(x+s_x\times1,y+s_y\times1)$上无任意一方的棋子停留，则$(x+s_x\times2,y+s_y\times2)$为一个可达的位置。

按照题面直接翻译成C++(Chinese->C++)，我们在walk_set[]中存放的就是${1,-1}$，然后直接枚举$s_x$和$s_y$，直接模拟。

for的双重循环直接枚举所有的$s_x$和$s_y$，可以直接套出上面描述中的两个点。

bool elephant_move(int start_x, int start_y, int end_x, int end_y)
{
    for (int x = 0; x < 2; x++)
        for (int y = 0; y < 2; y++)
        {
            if (belong[start_x + walk_set[x]][start_y + walk_set[y]] != NOT)
                continue;
            int to_x = start_x + (walk_set[x] << 1), to_y = start_y + (walk_set[y] << 1);
            if (end_x == to_x && end_y == to_y)
                return true;
        }
    return false;
}

马（horse） 的移动

题面中是这样写的

可达的位置至多8个，对于任意$s_x,s_y∈{1,-1}$，分别有：
- 如果位置$(x+s_x\times1,y)$上无任意一方的棋子停留，则$(x+s_x\times2,y+s_y\times1)$为一个可达的位置。
- 如果位置$(x,y+s_y\times1)$上无任意一方的棋子停留，则$(x+s_x\times1,y+s_y\times2)$为一个可达的位置。

(Chinese->C++)

操作同上，不难理解。

bool horse_move(int start_x, int start_y, int end_x, int end_y)
{
    for (int x = 0; x < 2; x++)
        for (int y = 0; y < 2; y++)
        {
            if (belong[start_x + walk_set[x]][start_y] != NOT)
                continue;
            int to_x = start_x + (walk_set[x] << 1), to_y = start_y + walk_set[y];
            if (end_x == to_x && end_y == to_y)
                return true;
        }
    for (int x = 0; x < 2; x++)
        for (int y = 0; y < 2; y++)
        {
            if (belong[start_x][start_y + walk_set[y]] != NOT)
                continue;
            int to_x = start_x + walk_set[x], to_y = start_y + (walk_set[y] << 1);
            if (end_x == to_x && end_y == to_y)
                return true;
        }
    return false;
}

车（car） 的移动

依旧简单，因为车可以在同一直线上不跨越其他棋子进行移动，所以我们对比起点和中点，选取他们相同的一维，在另一维上直接进行for判断直线上有无其他棋子停留。

bool car_move(int start_x, int start_y, int end_x, int end_y)
{
    if (start_x == end_x)
    {
        bool check = true;
        for (int y = min(start_y, end_y) + 1; y < max(start_y, end_y); y++)
            check &= belong[start_x][y] == NOT;
        if (check)
            return true;
    }
    if (start_y == end_y)
    {
        bool check = true;
        for (int x = min(start_x, end_x) + 1; x < max(start_x, end_x); x++)
            check &= belong[x][start_y] == NOT;
        if (check)
            return true;
    }
    return false;
}

鸭（duck） 的移动

题面中是这样写的

可达的位置至多8个，对于任意$s_x,s_y∈{1,-1}$，分别有：
- 如果位置$(x+s_x\times2,y+s_y\times1)$，$(x+s_x\times1,y)$上均无任意一方的棋子停留，则$(x+s_x\times3,y+s_y\times2)$为一个可达的位置。
- 如果位置$(x+s_x\times1,y+s_y\times2)$，$(x,y+s_y\times1)$上均无任意一方的棋子停留，则$(x+s_x\times2,y+s_y\times3)$为一个可达的位置。

(Chinese->C++)

操作与马相同，不难理解。

bool duck_move(int start_x, int start_y, int end_x, int end_y)
{
    for (int x = 0; x < 2; x++)
        for (int y = 0; y < 2; y++)
        {
            if (belong[start_x + (walk_set[x] << 1)][start_y + walk_set[y]] != NOT ||
                belong[start_x + walk_set[x]][start_y] != NOT)
                continue;
            int to_x = start_x + (walk_set[x] << 1) + walk_set[x], to_y = start_y + (walk_set[y] << 1);
            if (end_x == to_x && end_y == to_y)
                return true;
        }
    for (int x = 0; x < 2; x++)
        for (int y = 0; y < 2; y++)
        {
            if (belong[start_x + walk_set[x]][start_y + (walk_set[y] << 1)] != NOT ||
                belong[start_x][start_y + walk_set[y]] != NOT)
                continue;
            int to_x = start_x + (walk_set[x] << 1), to_y = start_y + (walk_set[y] << 1) + walk_set[y];
            if (end_x == to_x && end_y == to_y)
                return true;
        }
    return false;
}

兵（soldier） 的移动

士的可达的位置为$(x\pm1,y)$和$(x,y\pm1)$和$(x\pm1,y\pm1)$和$(x\pm1,y\mp1)$。

约等于王+士...

bool soldier_move(int start_x, int start_y, int end_x, int end_y)
{
    for (int x = 0; x < 2; x++)
    {
        int to_x = start_x + walk_set[x], to_y = start_y;
        if (end_x == to_x && end_y == to_y)
            return true;
    }
    for (int x = 0; x < 2; x++)
    {
        int to_x = start_x, to_y = start_y + walk_set[x];
        if (end_x == to_x && end_y == to_y)
            return true;
    }
    for (int x = 0; x < 2; x++)
    {
        int to_x = start_x + walk_set[x], to_y = start_y + walk_set[x];
        if (end_x == to_x && end_y == to_y)
            return true;
    }
    for (int x = 0; x < 2; x++)
    {
        int to_x = start_x + walk_set[x], to_y = start_y + walk_set[x ^ 1];
        if (end_x == to_x && end_y == to_y)
            return true;
    }
    return false;
}

（七个函数共4834B）

七个函数至此，让我们写一个处理函数来把七个函数凑一起。

bool choose(int start_x, int start_y, int end_x, int end_y)
{
    switch (board[start_x][start_y])
    {
    case captain:
        return captian_move(start_x, start_y, end_x, end_y);
        break;
    case guard:
        return guard_move(start_x, start_y, end_x, end_y);
        break;
    case elephant:
        return elephant_move(start_x, start_y, end_x, end_y);
        break;
    case horse:
        return horse_move(start_x, start_y, end_x, end_y);
        break;
    case car:
        return car_move(start_x, start_y, end_x, end_y);
        break;
    case duck:
        return duck_move(start_x, start_y, end_x, end_y);
        break;
    case soldier:
        return soldier_move(start_x, start_y, end_x, end_y);
        break;
    }
    return false;
}

通俗易懂

重要的处理

bool work(int start_x, int start_y, int end_x, int end_y, belong_type turn)
{
    if (GAME_OVER || belong[start_x][start_y] != turn || belong[end_x][end_y] == turn)
        return false;//游戏结束，或者这颗棋子不是自己的，或者目的地有自己的棋子
    if (!choose(start_x, start_y, end_x, end_y))
        return false;//如果不能移动
    chess moved_chess = board[end_x][end_y];//存放被移走的棋子
    board[end_x][end_y] = board[start_x][start_y];
    belong[end_x][end_y] = belong[start_x][start_y];
    board[start_x][start_y] = NA;
    belong[start_x][start_y] = NOT;
    if (moved_chess == captain)//如果王被移走，游戏结束
        GAME_OVER = true;
    CHECK_MATE = false;//开始准备判定将军局面
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 9; j++)
            if (belong[i][j] != NOT)//如果有棋子，我们直接判断它是否能攻击到对方王的位置
                CHECK_MATE |= choose(i, j, CAPTAIN_X[!belong[i][j]], CAPTAIN_Y[!belong[i][j]]);
    printf("%s %s;%s;%s;%s\n", rank_string[turn].c_str(), chess_string[board[end_x][end_y]].c_str(),
           moved_chess == NA ? "NA" : (rank_string[!turn] + " " + chess_string[moved_chess]).c_str(),
           CHECK_MATE ? "yes" : "no", GAME_OVER ? "yes" : "no");//输出
    return true;
}

这里便是游戏的主体回合，我们依次判定了移动是否可以进行，然后进行移动，然后判断将军局面和是否结束。

游戏结束了

主程序和初始化函数

void restart(void)
{
    for (int i = 0; i < 10; i++)
        for (int j = 0; j < 9; j++)
            belong[i][j] = NOT;
    board[0][4] = board[9][4] = captain;
    board[0][3] = board[0][5] = board[9][3] = board[9][5] = guard;
    board[0][2] = board[0][6] = board[9][2] = board[9][6] = elephant;
    board[0][1] = board[0][7] = board[9][1] = board[9][7] = horse;
    board[0][0] = board[0][8] = board[9][0] = board[9][8] = car;
    board[2][0] = board[2][8] = board[7][0] = board[7][8] = duck;
    board[3][0] = board[3][2] = board[3][4] = board[3][6] = board[3][8] =
        board[6][0] = board[6][2] = board[6][4] = board[6][6] = board[6][8] = soldier;
    belong[0][0] = belong[0][1] = belong[0][2] = belong[0][3] = belong[0][4] = belong[0][5] = belong[0][6] = belong[0][7] = belong[0][8] =
        belong[2][0] = belong[2][8] = belong[3][0] = belong[3][2] = belong[3][4] = belong[3][6] = belong[3][8] = RED;
    belong[9][0] = belong[9][1] = belong[9][2] = belong[9][3] = belong[9][4] = belong[9][5] = belong[9][6] = belong[9][7] = belong[9][8] =
        belong[7][0] = belong[7][8] = belong[6][0] = belong[6][2] = belong[6][4] = belong[6][6] = belong[6][8] = BLUE;
    CAPTAIN_X[RED] = 0;
    CAPTAIN_Y[RED] = 4;
    CAPTAIN_X[BLUE] = 9;
    CAPTAIN_Y[BLUE] = 4;
    GAME_OVER = false;
    return;
}

int main()
{
    int Q;
    scanf("%d", &Q);
    restart();
    belong_type turn = RED;
    while (Q--)
    {
        int start_x, start_y, end_x, end_y;
        scanf("%d%d%d%d", &start_x, &start_y, &end_x, &end_y);
        if (work(start_x, start_y, end_x, end_y, turn))
            if (turn == RED) //回合变化
                turn = BLUE;
            else
                turn = RED;
        else
            puts("Invalid command"); //不合法操作
    }
    return 0;
}

restart()函数就完全打表了，主程序也十分的通俗易懂。

完整代码：

赏

我缓慢吐出一串啊吧啊吧并不再想说话