Mr K marsh Discussions | Algorithms | HackerRank
We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. Mr K marsh
  5. Discussions

Mr K marsh

  • dehaka
     + 1 comment

    O(m^2 * n), only a bit better than brute force O(m^2 * n^2), there's probably a quadratic time algo but i cant be bothered to find it since O(m^2 * n) already pass all the test

    int kMarsh(int m, int n, const vector<string>& grid) {
    int longest = 0;
    vector<vector<int>> verticalx(m+1, vector<int>(n+1));
    for (int i=1; i <= m; i++) {
        for (int j=1; j <= n; j++) verticalx[i][j] = (grid[i-1][j-1] == 'x') ? i : verticalx[i-1][j];
    }
    for (int I=2; I <= m; I++) {
        vector<int> cache(I, -2);
        for (int J=2; J <= n; J++) {
            if (grid[I-1][J-2] == 'x') continue;
            if (grid[I-1][J-1] == 'x') {
                fill(cache.begin(), cache.end(), -2);
                continue;
            }
            for (int i=1; i < I; i++) {
                if (grid[i-1][J-1] == 'x' or grid[i-1][J-2] == 'x') {
                    cache[i] = -2;
                    continue;
                }
                if (cache[i] == -1 or cache[i] == -2) cache[i] = (verticalx[I][J-1] < i) ? J-1 : -1;
                if (cache[i] > 0 and verticalx[I][J] < i) longest = max(longest, 2 * (I-i+J-cache[i]));
            }
        }
    }
    return longest;
}

int main()
{
    vector<string> grid;
    int m, n;
    string temp;
    cin >> m >> n;
    for (int i=1; i <= m; i++) {
        cin >> temp;
        grid.push_back(temp);
    }
    int longest = kMarsh(m, n, grid);
    if (longest != 0) cout << longest;
    else cout << "impossible";
}