class Solution {
public:
    bool isRobotBounded(string instructions) {
        int x = 0, y = 0, d = 0;
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

        for (auto c: instructions) {
            if (c == 'G') x += dx[d], y += dy[d];
            else if (c == 'L') d = (d + 3) % 4;
            else d = (d + 1) % 4;
        }

        return !x && !y || d;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sum = 0;

    TreeNode* bstToGst(TreeNode* root) {
        if (!root) return NULL;
        bstToGst(root->right);
        sum += root->val;
        root->val = sum;
        bstToGst(root->left);
        return root;
    }
};

class Solution {
public:
    vector<int> gardenNoAdj(int n, vector<vector<int>>& paths) {
        vector<vector<int>> g(n);
        for (auto& p: paths) {
            int a = p[0] - 1, b = p[1] - 1;
            g[a].push_back(b);
            g[b].push_back(a);
        }

        vector<int> res(n);
        for (int i = 0; i < n; i ++ ) {
            bool st[5] = {};
            for (int j: g[i])
                st[res[j]] = true;

            for (int j = 1; j <= 4; j ++ )
                if (!st[j]) {
                    res[i] = j;
                    break;
                }
        }

        return res;
    }
};

class Solution {
public:
    vector<int> numMovesStonesII(vector<int>& stones) {
        vector<int> res(2);
        int n = stones.size();
        sort(stones.begin(), stones.end());
        int m = stones.back() - stones[0] - (n - 1);
        res[1] = m - min(stones[1] - stones[0] - 1, stones[n - 1] - stones[n - 2] - 1);

        res[0] = n;
        for (int i = 0, j = 0; i < n; i ++ ) {
            while (stones[i] - stones[j] + 1 > n) j ++ ;
            m = i - j + 1;

            int r;
            if (m == n - 1 && stones[i] - stones[j] == i - j) r = 2;
            else r = n - m;

            res[0] = min(res[0], r);
        }

        return res;
    }
};

class Solution {
public:
    int minScoreTriangulation(vector<int>& w) {
        int n = w.size();
        vector<vector<int>> f(n, vector<int>(n));

        for (int len = 3; len <= n; len ++ )
            for (int i = 0; i + len - 1 < n; i ++ ) {
                int j = i + len - 1;
                if (len == 3) f[i][j] = w[i] * w[j] * w[i + 1];
                else {
                    f[i][j] = 1e9;
                    for (int k = i + 1; k <= j - 1; k ++ )
                        f[i][j] = min(f[i][j], f[i][k] + f[k][j] + w[i] * w[k] * w[j]);
                }
            }

        return f[0][n - 1];
    }
};

class Solution {
public:

    int cross(int x1, int y1, int x2, int y2) {
        return x1 * y2 - x2 * y1;
    }

    bool isBoomerang(vector<vector<int>>& points) {
        auto &a = points[0], &b = points[1], &c = points[2];
        return cross(b[0] - a[0], b[1] - a[1], c[0] - a[0], c[1] - a[1]);
    }
};

class Solution {
public:
    unordered_set<string> S;
    int m, n = 1e6;

    string get(vector<int> p) {
        return to_string(p[0]) + ' ' + to_string(p[1]);
    }

    bool bfs(vector<int>& source, vector<int>& target) {
        auto st = S;

        queue<vector<int>> q;
        q.push(source);
        st.insert(get(source));

        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

        int cnt = 1;
        while (q.size()) {
            auto t = q.front();
            q.pop();

            for (int i = 0; i < 4; i ++ ) {
                int x = t[0] + dx[i], y = t[1] + dy[i];
                if (x >= 0 && x < n && y >= 0 && y < n && !st.count(get({x, y}))) {
                    ++ cnt;
                    if (cnt * 2 > m * (m - 1)) return true;
                    if (target[0] == x && target[1] == y) return true;

                    q.push({x, y});
                    st.insert(get({x, y}));
                }
            }
        }

        return false;
    }

    bool isEscapePossible(vector<vector<int>>& blocked, vector<int>& source, vector<int>& target) {
        for(auto& b: blocked) S.insert(get(b));
        m = blocked.size();
        return bfs(source, target) && bfs(target, source);
    }
};

class Solution {
public:
    vector<vector<int>> g;
    vector<vector<int>> st;  // 0未搜过；1：搜过；2：搜过且是边界
    int n, m;
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

    void dfs(int x, int y) {
        bool is_border = false;
        for (int i = 0; i < 4; i ++ ) {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && g[a][b] == g[x][y]) {
                if (!st[a][b]) {
                    st[a][b] = 1;
                    dfs(a, b);
                }
            } else {
                is_border = true;
            }
        }

        if (is_border) st[x][y] = 2;
    }

    vector<vector<int>> colorBorder(vector<vector<int>>& grid, int row, int col, int color) {
        g = grid;
        n = g.size(), m = g[0].size();
        st = vector<vector<int>>(n, vector<int>(m));

        st[row][col] = 1;
        dfs(row, col);

        for (int i = 0; i < n; i ++ )
            for (int j = 0; j < m; j ++ )
                if (st[i][j] == 2)
                    grid[i][j] = color;

        return grid;
    }
};

class Solution {
public:
    int maxUncrossedLines(vector<int>& a, vector<int>& b) {
        int n = a.size(), m = b.size();
        vector<vector<int>> f(n + 1, vector<int>(m + 1));

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ ) {
                f[i][j] = max(f[i - 1][j], f[i][j - 1]);
                if (a[i - 1] == b[j - 1])
                    f[i][j] = max(f[i][j], f[i - 1][j - 1] + 1);
            }

        return f[n][m];
    }
};

class Solution {
public:
    vector<int> numMovesStones(int a, int b, int c) {
        if (a > b) swap(a, b);
        if (a > c) swap(a, c);
        if (b > c) swap(b, c);

        vector<int> res(2);
        if (c - a == 2) res[0] = 0;
        else if (b - a <= 2 || c - b <= 2) res[0] = 1;
        else res[0] = 2;

        res[1] = c - a - 2;
        return res;
    }
};