语言月赛 202411 Enemy

题目概述¶

给定一个 n × m 的字符矩阵，代表战场局面，包含：

A：A 城士兵；
B：B 城士兵；
H：城墙；
#：空地。

每一行，A 城士兵总在左，B 城士兵在右，若存在城墙 H，必然在两者中间，且每行最多一个 H。

目标¶

模拟战斗全过程，最终输出战场的局势。

战斗阶段一：每行独立处理¶

对每一行进行处理，按照以下规则：

情况 1：本行存在城墙（防守）¶

双方各自撤回至己方边界，按顺序排列。
A 城士兵靠左紧凑排列；
B 城士兵靠右紧凑排列；
城墙 H 保留；
其余位置填充为 #。

例如：

输入: #A#AH#B# 输出: AA##H##B

情况 2：无城墙（进攻）¶

若 A 与 B 人数相等：双方全部消失。
若 A 多：B 全部消失，A 全员进攻靠右排列；
若 B 多：A 全部消失，B 全员进攻靠左排列；
其余位置填充为 #。

例如：

输入: #A##B#B# 输出: BB######

战斗阶段二：士兵消失判定¶

在第一阶段后，进行“邻接士兵”判断。

对于战场中剩余的 A 或 B：

如果它上方或下方与其相邻列有相同士兵（即“连线”），则它将消失；
所有士兵的判断是同时进行的。

注意：判断只考虑上下方向，左右方向无影响。

例如：

输入:

AAA

BBB

中间行无士兵，因此上、下方士兵不会消失。

实现思路总结¶

逐行统计每行的 A/B 数量和城墙位置；
根据是否有城墙决定处理逻辑（防守或进攻）；
使用二维数组存战场；
统一处理所有行后，进行“上下邻接判定”处理；
最终输出结果矩阵。

代码实现¶

#include <bits/stdc++.h>
using namespace std;

// 定义最大矩阵维度常量
constexpr int N = 1e3 + 5;

int n, m;         // n 行，m 列
char a[N][N];     // 战场地图矩阵

int main()
{
    // 输入矩阵大小
    cin >> n >> m;

    // 输入战场局势，注意从 1 开始编号，便于处理边界
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> a[i][j];

    // 第一阶段：处理每一行（撤退或进攻）
    for (int i = 1; i <= n; i++)
    {
        int y = 0;            // 城墙所在位置，若为 0 表示没有城墙
        int numa = 0, numb = 0;  // A/B 士兵计数

        // 统计该行的 A/B 数量，并找出城墙位置
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == 'H')
                y = j;
            if (a[i][j] == 'A')
                numa++;
            if (a[i][j] == 'B')
                numb++;
        }

        if (y) // 有城墙，双方撤退
        {
            // 左侧 numa 个 A 士兵
            for (int j = 1; j <= numa; j++)
                a[i][j] = 'A';
            // 城墙左边多余的位置置为 #
            for (int j = numa + 1; j < y; j++)
                a[i][j] = '#';
            // 右侧 numb 个 B 士兵，从右边向左排列
            for (int j = m; j >= m - numb + 1; j--)
                a[i][j] = 'B';
            // 城墙右边多余的位置置为 #
            for (int j = y + 1; j <= m - numb; j++)
                a[i][j] = '#';
        }
        else // 无城墙，双方进攻
        {
            if (numa == numb)
            {
                // A 和 B 数量相等，全灭
                for (int j = 1; j <= m; j++)
                    a[i][j] = '#';
            }
            else if (numa > numb)
            {
                // A 多，B 灭，A 向右推进
                for (int j = m; j >= m - numa + 1; j--)
                    a[i][j] = 'A';
                for (int j = m - numa; j >= 1; j--)
                    a[i][j] = '#';
            }
            else
            {
                // B 多，A 灭，B 向左推进
                for (int j = 1; j <= numb; j++)
                    a[i][j] = 'B';
                for (int j = numb + 1; j <= m; j++)
                    a[i][j] = '#';
            }
        }
    }

    // 第二阶段：上下相邻同类士兵消失
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (a[i][j] == 'A' || a[i][j] == 'B')
            {
                int nx = i + 1, ny = j;  // 下方的格子
                bool ok = 0;

                // 向下查找是否有相邻同类士兵
                while (nx <= n && a[nx][ny] == a[i][j])
                {
                    ok = 1;             // 标记可以消失
                    a[nx][ny] = '#';    // 下方士兵消失
                    nx++;
                }

                if (ok)
                    a[i][j] = '#';      // 当前士兵也消失
            }
        }
    }

    // 输出最终战场局势
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cout << a[i][j];
        }
        cout << "\n";
    }

    return 0;
}

复杂度分析¶

时间复杂度：$O(n \cdot m)$；
空间复杂度：$O(n \cdot m)$。

小技巧提示¶

预处理时记录每行 A/B 数目和城墙位置；
注意最后的“士兵消失”是同时进行的；
矩阵从 $1$ 开始编号是为了便于边界处理。

总结¶

这是一道模拟题，细节较多，关键在于：

分阶段进行模拟；
精确实现规则；
合理控制边界和同时判断的逻辑。

熟练掌握模拟类题目的处理方式，是刷题提升综合能力的重要一环。