大家好！

这是我自制的第二个题啦！

感谢大家的提交!!!

纪念一下两题：

第一题：

https://www.bcmakcspjs.top/p/LRX1

(小明看书)1级难度

第二题：

https://www.bcmakcspjs.top/p/LRX2

(关山万里)4级难度

正片开始

关山万里题解

题目背景

千年之前帝王一剑破开混沌、平定乱世，辽阔疆土之内烟火绵延。南疆河畔春风拂过万亩良田，北国雪峰常年沐浴天光，临水城池炊烟袅袅、百姓安居乐业。可荒凉荒原深处的蛮夷部族一直蛰伏窥视这片锦绣山河，时刻伺机进犯国土。 为守护国内黎民、筑起隔绝外敌的屏障，帝王下达诏令，首相负责工事规划：沿着整片帝国领土的外围修建长城。只要和国土八处方位相邻的地块属于蛮夷领地，就要在此修筑高墙，最终造就绵延不绝的万里关山。

题意简述

现在给定一张 $n$ 行、$m$ 列的网格地图，地图仅包含两种字符：

• \(\boldsymbol A\)：代表帝国管辖的领土；
• \(\boldsymbol B\)：代表境外蛮夷的土地；
• $\boldsymbol -$：修建完毕之后的防护长城。

长城修筑严格遵循以下全部规则：

1. 每一块帝国地块 \(\boldsymbol A\)，需要向周围八个方向进行探查：上下、左右、四个斜对角方位；
2. 如果探查之后的坐标超出地图边界，直接跳过该方位，不作任何操作；
3. 当探查位置原本为蛮夷土地 \(\boldsymbol B\)，就将该格子修改成长城标记 -；
4. 帝国领土 \(\boldsymbol A\) 全程保持原样，不可以改动；没有和国土相邻的蛮夷地块依旧保留字符 \(\boldsymbol B\)；
5. 全部施工结束之后，输出处理完成的完整工程地图。

解题思路

本题属于编程入门十分经典的八连通网格模拟题，核心思想就是遍历地图上每一处单元格，按照题目规则完成修改。

本题最容易踩入的致命陷阱

千万不能够一边修改地图、一边寻找帝国领土 \(\boldsymbol A\)的位置。 当我们把原本的 \(\boldsymbol B\) 修改成长城 -，工作数组的数据已经发生改动。如果依靠改动过后的地图去寻找国土点位，程序会出现逻辑错乱。 因此我们必须准备两份相互独立的网格：

1. ori：原始备份地图，全程不会改动，专门用来定位所有帝国领土 \(\boldsymbol A\)；
2. mp：工作操作地图，所有长城的铺设、单元格修改都在此完成。

八‑方向偏移数组

八个方位偏移：

int dx[8] = [-1, -1, -1, 0, 0, 1, 1, 1];
int dy[8] = [-1, 0, 1, -1, 1, -1, 0, 1];

完整分步算法流程

1. 读取地图的行数 n 和列数 m；
2. 读取每一行字符串，拷贝一份作为工作地图；
3. 双层循环遍历网格当中的每一处坐标；
4. 备份地图此处是 \(\boldsymbol A\)，则依次枚举八个方向；
5. 坐标合法，并且当前格子为 \(\boldsymbol B\)，修改为 -；
6. 打印最终地图。

C++代码

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

const int MAXN = 1005;
char origin[MAXN][MAXN];
char mp[MAXN][MAXN];

// 8个方向
int dx[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int dy[] = {-1, 0, 1, -1, 1, -1, 0, 1};

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; ++i)
    {
        cin >> origin[i];
        for (int j = 0; j < m; ++j)
        {
            mp[i][j] = origin[i][j];
        }
    }

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            if (origin[i][j] == 'A')
            {
                for (int k = 0; k < 8; ++k)
                {
                    int x = i + dx[k];
                    int y = j + dy[k];
                    if (x >= 0 && x < n && y >= 0 && y < m)
                    {
                        if (mp[x][y] == 'B')
                        {
                            mp[x][y] = '-';
                        }
                    }
                }
            }
        }
    }

    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < m; ++j)
        {
            cout << mp[i][j];
        }
        cout << endl;
    }
    return 0;
}

易错要点汇总

1. 一定要备份原始地图，依靠备份数组定位国土 \(\boldsymbol A\)；
2. 遍历八个方位，不要误写为上下左右四方向；
3. 只能够将字符 \(\boldsymbol B\) 修改成长城，国土 \(\boldsymbol A\) 保持原样；
4. C++堆区动态数组使用结束后逐层释放内存，规避内存泄漏。

谢谢大家的欣赏，我们下一题再见！

（下一题来啦！）

https://www.bcmakcspjs.top/p/LRX3001

第三题 首都速查 1级难度

谢谢大家！