A. Easy As ABC 题解

题意概述

给定一个 $3 \times 3$ 的字符网格，每个格子中都是 A、B、C 三者之一。

我们需要选出三个两两不同的格子，按顺序组成一个长度为 $3$ 的字符串，并满足：

• 第一个格子与第二个格子相邻；
• 第二个格子与第三个格子相邻。

这里的相邻不仅包括上下左右，还包括四个对角方向。

要求输出所有合法字符串中字典序最小的那个。

思路

这题是一个典型的小范围暴力题。

由于整个网格只有 $3 \times 3$，所以我们可以直接用六重循环枚举三个格子的坐标：

对每一组坐标，检查以下条件：

1. 三个格子互不相同；
2. 第一个格子和第二个格子相邻；
3. 第二个格子和第三个格子相邻。

如果满足条件，就把这三个格子上的字符拼成一个字符串，放进数组 V 中。

最后输出 V 中字典序最小的字符串即可。

如何判断相邻

若两个格子坐标分别是 $(r_1,c_1)$ 和 $(r_2,c_2)$，那么它们相邻，当且仅当：

并且这两个格子不是同一个格子。

这正好覆盖题目要求的八个方向。

正确性说明

六重循环会枚举出所有可能的三个格子顺序。

对于任意一个合法答案，它一定对应某三个具体格子，并且这三个格子一定会在枚举过程中被访问到。只要它们满足：

• 三个格子两两不同；
• 第一、第二个格子相邻；
• 第二、第三个格子相邻；

那么对应字符串就一定会被加入数组 V。

因此，所有合法的长度为 $3$ 的字符串都会被完整枚举出来，不会遗漏。

最后再对 V 取最小值，得到的自然就是字典序最小的合法答案。

思路

按照题解原意，做法可以概括为：

1. 初始化一个空数组 V；
2. 六重循环枚举三个格子的坐标；
3. 判断三个格子是否互不相同，以及相邻关系是否合法；
4. 若合法，则把对应字符串加入 V；
5. 输出 min_element(V.begin(), V.end())。

复杂度分析

设网格边长为 $N$。

由于需要枚举三个格子的行列坐标，总复杂度为：

本题中 $N=3$，因此这个复杂度完全足够。

总时间复杂度为：

空间复杂度为：

如果不存下所有候选字符串，而是边枚举边维护最小值，则额外空间也可以做到 $O(1)$。

参考代码

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

static bool adjacent(int r1, int c1, int r2, int c2) {
    if (r1 == r2 && c1 == c2) {
        return false;
    }
    return abs(r1 - r2) <= 1 && abs(c1 - c2) <= 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    vector<string> g(3);
    for (int i = 0; i < 3; ++i) {
        cin >> g[i];
    }

    vector<string> words;

    for (int r1 = 0; r1 < 3; ++r1) {
        for (int c1 = 0; c1 < 3; ++c1) {
            for (int r2 = 0; r2 < 3; ++r2) {
                for (int c2 = 0; c2 < 3; ++c2) {
                    if (r1 == r2 && c1 == c2) {
                        continue;
                    }
                    if (!adjacent(r1, c1, r2, c2)) {
                        continue;
                    }
                    for (int r3 = 0; r3 < 3; ++r3) {
                        for (int c3 = 0; c3 < 3; ++c3) {
                            if ((r3 == r1 && c3 == c1) || (r3 == r2 && c3 == c2)) {
                                continue;
                            }
                            if (!adjacent(r2, c2, r3, c3)) {
                                continue;
                            }

                            string cur = "";
                            cur += g[r1][c1];
                            cur += g[r2][c2];
                            cur += g[r3][c3];
                            words.push_back(cur);
                        }
                    }
                }
            }
        }
    }

    cout << *min_element(words.begin(), words.end()) << '\n';
    return 0;
}