【C++BFS 回溯】756. 金字塔转换矩阵

CSDN 2024-07-24 08:35:03 阅读 76

本文涉及知识点

C++BFS算法

C++回溯

LeetCode756. 金字塔转换矩阵

你正在把积木堆成金字塔。每个块都有一个颜色，用一个字母表示。每一行的块比它下面的行少一个块，并且居中。

为了使金字塔美观，只有特定的三角形图案是允许的。一个三角形的图案由两个块和叠在上面的单个块组成。模式是以三个字母字符串的列表形式 allowed 给出的，其中模式的前两个字符分别表示左右底部块，第三个字符表示顶部块。

例如，“ABC” 表示一个三角形图案，其中一个 “C” 块堆叠在一个 ‘A’ 块(左)和一个 ‘B’ 块(右)之上。请注意，这与 “BAC” 不同，“B” 在左下角，“A” 在右下角。

你从底部的一排积木 bottom 开始，作为一个单一的字符串，你必须使用作为金字塔的底部。

在给定 bottom 和 allowed 的情况下，如果你能一直构建到金字塔顶部，使金字塔中的每个三角形图案都是允许的，则返回 true ，否则返回 false 。

示例 1：

在这里插入图片描述

输入：bottom = “BCD”, allowed = [“BCC”,“CDE”,“CEA”,“FFF”]

输出：true

解释：允许的三角形模式显示在右边。

从最底层(第3层)开始，我们可以在第2层构建“CE”，然后在第1层构建“E”。

金字塔中有三种三角形图案，分别是“BCC”、“CDE”和“CEA”。都是允许的。

示例 2：

在这里插入图片描述

输入：bottom = “AAAA”, allowed = [“AAB”,“AAC”,“BCD”,“BBE”,“DEF”]

输出：false

解释：允许的三角形模式显示在右边。

从最底层(游戏邦注:即第4个关卡)开始，创造第3个关卡有多种方法，但如果尝试所有可能性，你便会在创造第1个关卡前陷入困境。

提示：

2 <= bottom.length <= 6

0 <= allowed.length <= 216

allowed[i].length == 3

所有输入字符串中的字母来自集合 {‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’}。

allowed 中所有值都是唯一的

C++BFS(极端情况超时)

BFS的状态表示：leves[i]记录倒数第0层所有可能。所有的状态数为：mⁿ,n = bottom.length， ,m = 7(A到G)即空间复杂度为：O(mⁿ)。

BFS的后续状态：所有可能的倒数i+1层。一个状态对应的后续状态：(n-1)^m。每种状态：组织字符串，时间复杂度O(n),出重大约O(10)，故总时间复杂度为：O(mⁿn^m10n)，理论上严重超时，实际略微超时。

BFS的初始状态：leves = { {bottom}}。

BFS的返回值：任意leves[i]为空，返回false；否则返回true。

BFS的重复处理： leves[i]的长度为：bottom.length - i，故当i

≠

\neq

= j是，leves[i]的任意元素不会和leves[j]相同。只需要处理leves[i]内部的重复。

unorder_map<string,vector> mAllow。 key是：allower.substr(0,2) value是：allower[2]。

代码

<code>class Solution {

public:

bool pyramidTransition(string bottom, vector<string>& allowed) {

unordered_map<string, vector<char>> mAllow;

for (const auto& str : allowed) {

mAllow[str.substr(0, 2)].emplace_back(str[2]);;

}

vector<vector<string>> leves = { { bottom} };

for (int i = 0; i+1 < bottom.length(); i++) {

unordered_set<string> nexts;

std::function<void(string&,const string&, int)> BackTrack = [&](string& str,const string& cur, int begin) {

if (begin + 1 == cur.length()) {

if(-1 == str.find(' ')){ nexts.emplace(str); }

return;

}

for (const auto& ch : mAllow[cur.substr(begin, 2)]) {

str[begin] = ch;

BackTrack(str, cur, begin + 1);

}

};

for (const auto& cur : leves[i]) {

string str(cur.length() - 1, ' ');

BackTrack(str, cur, 0);

}

if (nexts.empty()) { return false; }

leves.emplace_back(vector<string>(nexts.begin(), nexts.end()));

}

return true;

}

};

单元测试

string bottom;

vector<string> allowed;

TEST_METHOD(TestMethod1)

{

bottom = "BCD", allowed = { "BCC", "CDE", "CEA", "FFF" };