IBM Oa Help | Oa Exam Helper

def calculateTotalRegion(heights):
    n = len(heights)
    left = [-1] * n
    right = [n] * n
    stack = []
    for i in range(n):
        while stack and heights[stack[-1]] < heights[i]:
            right[stack.pop()] = i
        stack.append(i)
    stack.clear()
    for i in range(n - 1, -1, -1):
        while stack and heights[stack[-1]] < heights[i]:
            left[stack.pop()] = i
        stack.append(i)
    
    total = 0
    for i in range(n):
        region_length = right[i] - left[i] - 1
        total += region_length

    return total

#include <iostream>
#include <queue>
#include <vector>
#include <tuple>
#include <climits>

using namespace std;

struct Point {
    int x, y;
};

const vector<Point> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
vector<vector<int>> bfs(const vector<vector<int>>& maze, Point start) {
    int n = maze.size();
    int m = maze[0].size();
    vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
    queue<Point> q;
    q.push(start);
    dist[start.x][start.y] = 0;

    while (!q.empty()) {
        Point current = q.front();
        q.pop();

        for (auto dir : directions) {
            int newX = current.x + dir.x;
            int newY = current.y + dir.y;
            if (newX >= 0 && newX < n && newY >= 0 && newY < m && maze[newX][newY] != 1) {
                if (dist[newX][newY] > dist[current.x][current.y] + 1) {
                    dist[newX][newY] = dist[current.x][current.y] + 1;
                    q.push({newX, newY});
                }
            }
        }
    }
    
    return dist;
}

int minMoves(vector<vector<int>>& maze, int x, int y) {
    int n = maze.size();
    int m = maze[0].size();
    vector<Point> coins;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (maze[i][j] == 2) {
                coins.push_back({i, j});
            }
        }
    }

    int coinCount = coins.size();
    if (coinCount == 0) {
        auto dist = bfs(maze, {0, 0});
        return dist[x][y] == INT_MAX ? -1 : dist[x][y];
    }

    vector<Point> positions = {{0, 0}};  
    positions.insert(positions.end(), coins.begin(), coins.end());
    positions.push_back({x, y}); 
    int pSize = positions.size();
    vector<vector<int>> distMatrix(pSize, vector<int>(pSize, INT_MAX));

    for (int i = 0; i < pSize; ++i) {
        auto dist = bfs(maze, positions[i]);
        for (int j = 0; j < pSize; ++j) {
            distMatrix[i][j] = dist[positions[j].x][positions[j].y];
        }
    }
    for (int i = 0; i < pSize; ++i) {
        for (int j = 0; j < pSize; ++j) {
            if (distMatrix[i][j] == INT_MAX) {
                return -1;
            }
        }
    }
    int coinMaskSize = 1 << coinCount;
    vector<vector<int>> dp(coinMaskSize, vector<int>(coinCount, INT_MAX));
    for (int i = 0; i < coinCount; ++i) {
        dp[1 << i][i] = distMatrix[0][i + 1];  
    }
    for (int mask = 0; mask < coinMaskSize; ++mask) {
        for (int i = 0; i < coinCount; ++i) {
            if (!(mask & (1 << i))) continue;  
            for (int j = 0; j < coinCount; ++j) {
                if (mask & (1 << j)) continue;  
                int newMask = mask | (1 << j);
                dp[newMask][j] = min(dp[newMask][j], dp[mask][i] + distMatrix[i + 1][j + 1]);
            }
        }
    }
    int minSteps = INT_MAX;
    for (int i = 0; i < coinCount; ++i) {
        minSteps = min(minSteps, dp[coinMaskSize - 1][i] + distMatrix[i + 1][pSize - 1]);
    }

    return minSteps;
}