# 756. Pyramid Transition Matrix

We are stacking blocks to form a pyramid. Each block has a color which is a one letter string.

We are allowed to place any color block `C` on top of two adjacent blocks of colors `A` and `B`, if and only if `ABC` is an allowed triple.

We start with a bottom row of `bottom`, represented as a single string. We also start with a list of allowed triples `allowed`. Each allowed triple is represented as a string of length 3.

Return true if we can build the pyramid all the way to the top, otherwise false.

**Example 1:**

```
Input: bottom = "BCD", allowed = ["BCG", "CDE", "GEA", "FFF"]
Output: true
Explanation:
We can stack the pyramid like this:
    A
   / \
  G   E
 / \ / \
B   C   D

We are allowed to place G on top of B and C because BCG is an allowed triple.  Similarly, we can place E on top of C and D, then A on top of G and E.
```

**Example 2:**

```
Input: bottom = "AABA", allowed = ["AAA", "AAB", "ABA", "ABB", "BAC"]
Output: false
Explanation:
We can't stack the pyramid to the top.
Note that there could be allowed triples (A, B, C) and (A, B, D) with C != D.
```

**Note:**

1. `bottom` will be a string with length in range `[2, 8]`.
2. `allowed` will have length in range `[0, 200]`.
3. Letters in all strings will be chosen from the set `{'A', 'B', 'C', 'D', 'E', 'F', 'G'}`.

```cpp
// Backtracking
bool helper(const string& cur, string above, unordered_map<string, unordered_set<char> >& mp) {
    if (cur.length() == 2 && above.length() == 1) return true;
    if (cur.length() - 1 == above.length()) return helper(above, "", mp);
    int pos = above.length();
    const string& base = cur.substr(pos, 2);
    for (const char& ch : mp[base]) {
        if (helper(cur, above + string(1, ch), mp)) return true;
    }
    return false;
}
bool pyramidTransition(string bottom, vector<string>& allowed) { // time: O(7^( (bottom_len - 1)! ) ); space: O(bottom_len - 1) + O(# of blocks in allowed)
    unordered_map<string, unordered_set<char> > mp;
    for (const string& str : allowed) mp[str.substr(0, 2)].insert(str[2]);
    return helper(bottom, "", mp);
}
```

```cpp
// Iteration DP
bool pyramidTransition(string bottom, vector<string>& allowed) { // time: O(n^2); space: O(n^2); n: bottom length
    int n = bottom.size();
    vector<vector<vector<bool> > > dp(n, vector<vector<bool> >(n, vector<bool>(7, false) ) );
    unordered_map<char, unordered_set<string> > mp;
    for (const string& str : allowed) mp[str[2]].insert(str.substr(0, 2));
    for (int i = 0; i < n; ++i) dp[n - 1][i][bottom[i] - 'A'] = true;
    for (int i = n - 2; i >= 0; --i) {
        for (int j = 0; j <= i; ++j) {
            for (char ch = 'A'; ch <= 'G'; ++ch) {
                if (!mp.count(ch)) continue;
                for (const string& str : mp[ch]) {
                    if (dp[i + 1][j][str[0] - 'A'] && dp[i + 1][j + 1][str[1] - 'A']) 
                        dp[i][j][ch - 'A'] = true;
                }
            }
        }
    }
    for (int i = 0; i < 7; ++i) {
        if (dp[0][0][i]) return true;
    }
    return false;
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/backtracking/756.-pyramid-transition-matrix.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.