LG5380 [THUPC2019]鸭棋

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


题面

黑色大模拟一题,身为大模拟爱好者的我当然要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()函数就完全打表了,主程序也十分的通俗易懂

完整代码:


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