6.1 模拟

在我看来，模拟不是一种算法，而更像是一项重要的技术，它非常考验用计算机解决问题的能力。在初学者大面积应用暴力枚举方法解题时，熟练模拟题意写出程序是一条必经之路。

6.1.1 螺旋前进模拟

例题：蓝桥 基础练习 回形取数

问题描述

回形取数就是沿矩阵的边取数，若当前方向上无数可取或已经取过，则左转90度。一开始位于矩阵左上角，方向向下。

输入格式

输入第一行是两个不超过200的正整数m, n，表示矩阵的行和列。接下来m行每行n个整数，表示这个矩阵。

输出格式

输出只有一行，共 个数，为输入矩阵回形取数得到的结果。数之间用一个空格分隔，行末不要有多余的空格。

样例输入 3 3 1 2 3 4 5 6 7 8 9

样例输出 1 4 7 8 9 6 3 2 5

样例输入 3 2 1 2 3 4 5 6

样例输出 1 3 5 6 4 2

这一题是经典的蓝桥式模拟，初学者很容易将代码写得冗长，且难以调试。方向数组的技巧可以帮助你把四种情况写成一种情况。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 204;
const int inf = 0x3f3f3f3f;
// 方向数组
const int dx[] = {1, 0, -1, 0};
const int dy[] = {0, 1, 0, -1};
int a[N][N];
int n, m;
int k = 0;          // 当前方向
int x = 1, y = 1;   // 当前位置
int main() {
    cin >> n >> m;
    // 将边界初始化为无效值，方便边界判断
    for (int i=0; i<=n+1; ++i) {
        for (int j=0; j<=m+1; ++j) {
            a[i][j] = -inf;
        }
    }
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=m; ++j) {
            cin >> a[i][j];
        }
    }
    // 输出所有的数，共 m*n 个
    for (int i=0; i<m*n; ++i) {
        cout << a[x][y] << ' ';    // 单行输出，最后可以多输出一个空格
        a[x][y] = -inf;        // 访问过标记为无效值
        // 当前方不通时，转向
        if (a[x + dx[k]][y + dy[k]] == -inf) {
            k = (k + 1) % 4;
        }
        // 按方向前进
        x += dx[k];
        y += dy[k];
    }
    return 0;
}

代码中，把比实际存储范围大一圈的数组，整个初始化为负无穷值，这一时间开销和读入相当，可以接受。实际上，这一操作的目的只是把边界置为无效值。这种写法比较简便，当然你也可以写成：

for (int i=0; i<=m+1; ++i) {
    a[i][0] = -inf;
    a[i][n+1] = -inf;
}
for (int i=0; i<=n+1; ++i) {
    a[0][i] = -inf;
    a[m+1][i] = -inf;
}

这样，你的确为程序节省了无用的操作，但显然把简单的事情变得更加复杂了。

值得一提的是本题选择的无效值不能是数组默认值 0，因为部分用例的矩阵包含 0 。（正式比赛一般会告知数据范围）

另一方面，这里的 a[][] 在后面同样起到了 vis[][] 的作用（我把 a[i][j] == -inf 的情况定义为 vis[i][j] == true ）。也许你会觉得它们各自分开来写，逻辑会更清晰，但在后面「前方是否可通行」的判断，就要再加上 && !vis[x + dx[k]][y + dy[k]]，这也增加了代码量。但事实上，他们完全可以用一种定义表示——如果 a[i][j] != -inf，它就是可读出数的、可通行的位置。

我希望传达的是，在熟练使用语言方面进步时，你会自然而然地写出具有简洁之美的代码。你可以在网上搜索此题，很多人写出的代码，使得作者本人都不一定愿意维护，这样的代码在赛场上一旦出错，会极大增加思考负担、增长焦躁情绪，你甚至可能做出全部重写（改用更简洁的结构）的决定，失去很多宝贵的时间。

关于「方向数组」技巧，你可以模拟程序运行，仔细体会它的精妙设计。它其实是关于前进方向在四个状态之间的不断转移。

这种顺序的转移体现为 k = (k + 1) % 4; 这句代码。

根据题目要求方向次序的不同，你需要写出对应的方向数组，确定转移的规则。一旦程序确认当前方向，可以方便的从方向数组获知当前方向需要 **x** 与 **y** 的改变量，这也是数组元素值的定义。

练习：兰顿蚂蚁【第五届】【省赛】

你是否已经熟练运用方向数组？

参考代码

#include <iostream>
using namespace std;
const int N = 104;
const int dx[] = {0, 1, 0, -1};
const int dy[] = {1, 0, -1, 0};
bool a[N][N];
int n, m;
int x, y;
int k;
void move() {
    if (a[x][y]) {    // 当前黑格
        k = (k + 1) % 4;
    } else {        // 当前白格
        k = (k + 3) % 4;
    }
    a[x][y] ^= 1;    // 当前格变为相反的颜色 位运算操作
    // 前进
    x += dx[k];
    y += dy[k];
}
int main() {
    cin >> n >> m;
    for (int i=0; i<n; ++i) {
        for (int j=0; j<m; ++j) {
            cin >> a[i][j];
        }
    }
    cin >> x >> y;
    // 读入初始方向
    char c;
    cin >> c;
    switch (c) {
    case 'U':
        k = 3;
        break;
    case 'D':
        k = 1;
        break;
    case 'L':
        k = 2;
        break;
    case 'R':
        k = 0;
        break;
    }
    // 读入步数
    int step;
    cin >> step;
    while (step--) {
        move();        // 使用万能头文件的情况，请避免命名为 move
    }
    cout << x << ' ' << y << endl;
    return 0;
}

6.1.2 日期模拟

例题 1：日期问题【第八届】【省赛】

小明正在整理一批历史文献。这些历史文献中出现了很多日期。小明知道这些日期都在1960年1月1日至2059年12月31日。令小明头疼的是，这些日期采用的格式非常不统一，有采用年/月/日的，有采用月/日/年的，还有采用日/月/年的。更加麻烦的是，年份也都省略了前两位，使得文献上的一个日期，存在很多可能的日期与其对应。

比如02/03/04，可能是2002年03月04日、2004年02月03日或2004年03月02日。

给出一个文献上的日期，你能帮助小明判断有哪些可能的日期对其对应吗？

输入格式
一个日期，格式是"AA/BB/CC"。 (0 <= A, B, C <= 9)

输入格式
输出若干个不相同的日期，每个日期一行，格式是"yyyy-MM-dd"。多个日期按从早到晚排列。

样例输入
02/03/04

样例输出
2002-03-04
2004-02-03
2004-03-02

本体的核心思路是：遍历 1960年1月1日 至 2059年12月31日 之间的所有日期。逐一检查合法日期是否能够对应输入字符串。注意日期从 1 月 1 日起，因此本题的简单做法是多重 for 循环遍历，遍历得到的日期一定是合法日期。

参考代码

#include <iostream>
#include <string>
using namespace std;
// [1, 12]每个月份的天数 
const int md[] = {0, 31, 29, 31, 30, 31, 30 ,31, 31, 30, 31, 30, 31};
int a, b, c;
// 判断闰年
bool isrun(int y) {
    return y % 4 == 0 && y % 100 != 0 || y % 400 == 0;
}
// 分别检查输入的 a/b/c 可能的三种解读
bool check(int y, int m, int d) {
    // a,b,c 分别是:
    // 年/月/日
    if (a == y && b == m && c == d) {
        return true;
    }
    // 月/日/年
    if (a == m && b == d && c == y) {
        return true;
    }
    // 日/月/年
    if (a == d && b == m && c == y) {
        return true;
    }
    return false;
}
// 按题目格式输出
void print(int y, int m, int d) {
    cout << y << '-';
    if (m < 10) {
        cout << '0';
    }
    cout << m << '-';
    if (d < 10) {
        cout << '0';
    }
    cout << d << endl;
}
int main() {
    string s;
    cin >> s;
    // 直接按对应位置提取三个数字
    a = (s[0] - '0') * 10 + (s[1] - '0');
    b = (s[3] - '0') * 10 + (s[4] - '0');
    c = (s[6] - '0') * 10 + (s[7] - '0');
    for (int y=1960; y<=2059; ++y) {
        for (int m=1; m<=12; ++m) {
            for (int d=1; d<=md[m]; ++d) {
                // 不是闰年的情况，跳过2月29日
                if (m == 2 && d == 29 && !isrun(y)) {
                    break;
                }
                // 检查当前日期
                if (check(y % 100, m, d)) {
                    print(y, m, d);
                }
            }
        }
    }
    return 0;
}

例题 2：回文日期【第十一届】【省赛】

问题描述

2020年春节期间，有一个特殊的日期引起了大家的注意：2020年2月2日。因为如果将这个日期按 yyyymmdd 的格式写成一个8位数是 20200202，恰好是一个回文数。我们称这样的日期是回文日期。

有人表示 20200202 是“千年一遇”的特殊日子。对此小明很不认同，因为不到2年之后就是下一个回文日期：20211202 即2021年12月2日。

也有人表示 20200202 并不仅仅是一个回文日期，还是一个 ABABBABA 型的回文日期。对此小明也不认同，因为大约 100 年后就能遇到下一个 ABABBABA 型的回文日期：21211212 即2121年12月12日。算不上“千年一遇”，顶多算“千年两遇”。

给定一个8位数的日期，请你计算该日期之后下一个回文日期和下一个 ABABBABA 型的回文日期各是哪一天。

输入格式

输入包含一个八位整数 N，表示日期。

输出格式

输出两行，每行1个八位数。
第一行表示下一个回文日期，第二行表示下一个 ABABBABA 型的回文日期。

样例输入

20200202

样例输出

20211202 21211212

评测用例规模与约定

对于所有评测用例，10000101≤N≤89991231， 保证 N 是一个合法日期的 8 位数表示。

本题中仍然要遍历范围内的日期，不同点是，起始时间不固定，使用 for 循环不方便。我们这次换一种更加暴力的思路：枚举日期串，再判断合法性。我们枚举的范围可以是 。这样一来主程序的逻辑十分清晰。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int md[] = {0, 31, 29, 31, 30, 31, 30 ,31, 31, 30, 31, 30, 31};
bool found;
int x;
bool isrun(int y) {
    return y % 4 == 0 && y % 100 != 0 || y % 400 == 0;
}
// 判断是否是合法日期
bool valid(int n) {
    int y = n / 10000;
    int m = n / 100 % 100;
    // 月份范围 [1, 12]
    if (m < 1 || m > 12) {
        return false;
    }
    int d = n % 100;
    // 日期范围 [1, 29-31]（根据月份）
    if (d < 1 || d > md[m]) {
        return false;
    }
    // 排除不是闰年的 2月29日
    if (!isrun(y) && m == 2 && d == 29) {
        return false;
    }
    return true;
}
// 回文串无所谓正反，拆出来的字符串不用 reverse
string to_str(int x) {
    string res;
    while (x) {
        res += '0' + x % 10;
        x /= 10;
    }
    // reverse(res.begin(), res.end());
    return res;
}
// 判断回文，回文串正反应当相同
bool palindrome(int n) {
    string s = to_str(n);
    string t = s;                    // 拷贝一份
    reverse(s.begin(), s.end());    // 反转一个字符串
    return s == t;
}
bool ababbaba(int n) {
    string s = to_str(n);
    // 隔一位应当相同
    if (s[0] != s[2] || s[1] != s[3]) {
        return false;
    }
    // 相邻应当不同
    if (s[0] == s[1]) {
        return false;
    }
    return true;
}
int main() {
    cin >> x;
    // 从输入的下一天枚举日期串
    for (int i=x+1; i<=99991231; ++i) {
        // 判断合法 + 是回文串
        if (valid(i) && palindrome(i)) {
            // 只输出第一次找到的回文串
            if (!found) {
                cout << i << endl;
                found = true;
            }
            // 找到 ab... 串，程序结束
            if (ababbaba(i)) {
                cout << i << endl;
                break;
            }
        } 
    }
    return 0;
}

还是像前面说的一样——越是暴力的方法，就越可靠。这个方法同样可以解决「例题 1」，代价是写出 is_valid() 函数。这样的题型会让你多花费些笔墨，但思维上并不复杂，前提是你动手敲代码前理出清晰的思路。

另外，你也可以像「例题 1」的方法，不使用 for 循环写出「模拟日期」（你可以使用一些变量，或者一个类，关键是 nextDay() 方法让日期来到下一天），会得到更优的时间复杂度。这种方法还可以考虑到「星期几」这一变量。

该方法请参考：日期模拟