题意分析

题目给定一个由堆叠画框组成的图像，画框用大写字母标记且每个画框宽度为 1 个字符，边框长度不短于 3 个字符，每个画框四条边至少有一部分可见，要求根据给定图像确定画框从下到上的堆叠顺序。输入包含多个图像块，每个图像块由高度 h、宽度 w 以及 h 个长度为 w 的字符串组成。输出要求按画框从下到上的堆叠顺序输出画框字母，若有多种可能顺序则按字母顺序全部列出，每个输入块至少存在一种合法顺序。

解题思路

1. 初始化：在 init 函数中对一些全局变量进行初始化，包括清空存储图关系的 vector 数组 v、将每个节点的入度 degree 置为 0、访问标记 vis 置为 0、计数数组 cnt 置为 0 以及节点数量 n 置为 0。
2. 构建图：
   • 遍历 26 个大写字母，对于每个字母 id，先找出其在图像中出现的最上、最下、最左、最右的位置。若该字母在图像中出现，则将其对应的 vis 标记为 1。
   • 然后遍历该字母边框位置（上下左右边），若遇到其他字母，则建立从当前字母到该字母的有向边，即将该字母的编号加入当前字母对应的 vector 中，并将该字母的入度 degree 加 1。
3. 拓扑排序：
   • 统计出现的字母数量 n。
   • 从入度为 0 且未被访问过的节点开始进行拓扑排序。在 topsort 函数中，将当前节点加入结果数组 ans 中，若达到了 n 个节点（即找到了一种完整的堆叠顺序），则输出该顺序。
   • 在递归调用拓扑排序之前，将当前节点的所有出边对应的节点入度减 1，递归结束后再将入度加回来，同时对当前节点的访问计数 cnt 进行相应增减，以处理多种可能顺序的情况。

复杂度分析

1. 时间复杂度：
   • 初始化部分时间复杂度为 $O(26)$，因为要对 26 个字母相关的变量进行初始化。
   • 构建图部分，对于每个字母，在图像中查找其位置以及建立边的操作，图像大小为 $h \times w$，时间复杂度为 $O(26 \times h \times w)$。
   • 拓扑排序部分，每个节点最多被访问一次，每次访问时对其出边进行操作，时间复杂度为 $O(26 \times 26)$（因为节点最多 26 个）。
   • 总体时间复杂度为 $O(26 \times h \times w + 26 \times 26)$。
2. 空间复杂度：
   • 存储图关系的 vector 数组 v 最多存储 $26 \times 26$ 条边，空间复杂度为 $O(26 \times 26)$。
   • 其他变量如 degree、vis、cnt 等数组大小为 26，空间复杂度为 $O(26)$。
   • 总体空间复杂度为 $O(26 \times 26 + 26) = O(26 \times 26)$。

代码实现

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <queue>
#include <functional>
#include <vector>
#include <stack>
#include <set>
#include <bitset>
//#define int long long
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 50;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const int HASH = 131;

string s[40];
vector<int> v[30];
int degree[30] = {0};
int vis[30] = {0};
int h, w, n;
int cnt[30] = {0};

void init()
{
    n = 0;
    for (int i = 0; i <= 26; i++)
    {
        v[i].clear();
        degree[i] = 0;
        vis[i] = 0;
        cnt[i] = 0;
    }
}

char ans[30];

void topsort(int tmp, int depth)
{
    ans[depth] = tmp + 'A';

    if (depth == n - 1)
    {
        cout << ans << endl;
        return;
    }
    cnt[tmp]++;
    for (int i = 0; i < v[tmp].size(); i++)
    {
        int t = v[tmp][i];
        --degree[t];
    }
    for (int i = 0; i < 26; i++)
        if (vis[i] && degree[i] == 0 &&!cnt[i])
            topsort(i, depth + 1);
    for (int i = 0; i < v[tmp].size(); i++)
    {
        int t = v[tmp][i];
        ++degree[t];
    }
    cnt[tmp]--;
}

int main()
{
    while (scanf("%d %d", &h, &w) != EOF)
    {
        init();
        for (int i = 0; i < h; i++)
            cin >> s[i];
        for (int num = 0; num < 26; num++)
        {
            char id = num + 'A';
            int shang = 100, xia = -1, zuo = 100, you = -1;
            for (int i = 0; i < h; i++)
            {
                for (int j = 0; j < w; j++)
                {
                    if (s[i][j] == id)
                    {
                        shang = min(i, shang);
                        xia = max(i, xia);
                        zuo = min(j, zuo);
                        you = max(j, you);
                    }
                }
            }
            if (shang != 100)
                vis[num] = 1;
            for (int i = zuo; i <= you; i++)
            {
                if (s[shang][i] != id)
                {
                    int id1 = id - 'A';
                    int id2 = s[shang][i] - 'A';
                    v[id1].push_back(id2);
                    degree[id2]++;
                }
                if (s[xia][i] != id)
                {
                    int id1 = id - 'A';
                    int id2 = s[xia][i] - 'A';
                    v[id1].push_back(id2);
                    degree[id2]++;
                }
            }
            for (int i = shang; i <= xia; i++)
            {
                if (s[i][zuo] != id)
                {
                    int id1 = id - 'A';
                    int id2 = s[i][zuo] - 'A';
                    v[id1].push_back(id2);
                    degree[id2]++;
                }
                if (s[i][you] != id)
                {
                    int id1 = id - 'A';
                    int id2 = s[i][you] - 'A';
                    v[id1].push_back(id2);
                    degree[id2]++;
                }
            }
        }
        for (int i = 0; i < 26; i++)
            if (vis[i])
                n++;
        ans[n] = '\0';
        for (int i = 0; i < 26; i++)
        {
            if (vis[i] && degree[i] == 0)
                topsort(i, 0);
        }
    }
    return 0;
}