COCI '20 Contest 3 #4 Selotejp

 Problem Link

Algorithms used: DP

In this problem, we are given an N by M grid. There are some "marked" cells that we need to cover using tape. The tape can only be applied horizontally or vertically, cannot cover "unmarked" cells and a marked cell cannot be covered by more than one piece of tape. We need to find the minimum number of pieces of tape required to cover every marked cell such that the above conditions are satisfied.

We can solve this problem using DP. Usually, when the constraints on a variable are small (less than 20), we can expect bitmask DP to be part of the solution. It's no different here. I solve this problem recursively.

We can go over every cell of the grid from top to bottom, left to right and maintain a bitmask that tells us which cells, from all the cells from (i-1, j) to (i, j-1), have been covered by a vertical piece of tape (signified by a 1 bit in the mask) or a horizontal piece of tape (signified by a 0 bit in the mask). If a cell is unmarked a 0 bit will also signify this.

Looking at the cell (i, j), if it's unmarked, then we can skip this cell as we can't cover this with any tape. To transition, we need to look at the next cell (which will either be (i+1, 0) if the current cell is the last one in row i or will be cell (i, j+1) if the current cell is not the last one in row i) and adjust the bitmask. Notice how we needn't know about what kind of tape cell (i-1, j) is covered by once we move to the next cell, which is signified by the left most bit of the bitmask. So for the transition, we can simply discard the leftmost bit and shift the remaining bits 1 position to the left. To do this, if the leftmost value of the mask is 1, then we subtract (1 << (m+1)) from the mask (because the length of the mask will be (m+1), and set

new_mask = mask << 1;

Since we aren't covering this cell with tape, we can let the last bit be 0.

On the other hand, if the cell (i, j) is marked, then we need to cover it with a piece of tape. We essentially have 4 options:

1. Cell (i-1, j), which is the cell located above (i, j), is covered with a piece of vertical tape which we can extend to cover this cell
2. Cell (i, j-1), which is the cell located to the left of (i, j) is covered with a piece of horizontal tape which we can extend to cover this cell
3. We start a new piece of horizontal tape at this cell
4. We start a new piece of vertical tape at this cell

For options 1 and 4, we need to ensure that the last bit of new_mask is 1 to indicate that this cell is covered with a vertical piece of tape and that for options 2 and 3, the bit is 0. For options 3 and 4 we also need to add 1 to the answer for the additional piece we are starting.

Code

#include <bits/stdc++.h>

using namespace std;

int n, m;

vector <string> grid;

const int maxn = 1000 + 1;

const int maxm = 10 + 1;

const int maxmask = (1 << 11) + 1;

int dp[maxn][maxm][maxmask];

bool ready[maxn][maxm][maxmask];

int solve(int i, int j, int mask) {

    if (i > n || j > m || i <= 0 || j <= 0)

        return 0;

    if (ready[i][j][mask])

        return dp[i][j][mask];

    int ans = 1e9;

    if (grid[i][j] == '.') {

        int newmask = mask;

        if (newmask & (1 << (m-1)))

            newmask -= (1 << (m-1));

        newmask = (newmask << 1);

        if (j == m)

            ans = solve(i+1, 1, newmask);

        else

            ans = solve(i, j+1, newmask);

    } else {

        // see if you can cover it using a piece of vertical tape

        if (mask & (1 << (m-1))) {

            int newmask = mask;

            newmask -= (1 << (m-1));

            newmask = (newmask << 1);

            newmask++;

            if (j == m)

                ans = solve(i+1, 1, newmask);

            else

                ans = solve(i, j+1, newmask);

        } else {

            // cover it with a piece of vertical tape

            int newmask = mask;

            newmask = (newmask << 1);

            newmask++;

            if (j == m)

                ans = solve(i+1, 1, newmask) + 1;

            else

                ans = solve(i, j+1, newmask) + 1;

        }

        // see if you can use a piece of horizontal tape

        if (mask % 2 == 0 && j-1 >= 1 && grid[i][j-1] == '#') {

            // continue the existing piece of tape;

            int newmask = mask;

            if (newmask & (1 << (m-1)))

                newmask -= (1 << (m-1));

            newmask = (newmask << 1);

            if (j == m)

                ans = min(ans, solve(i+1, 1, newmask));

            else

                ans = min(ans, solve(i, j+1, newmask));

        } else {

            // start your own horizontal tape

            int newmask = mask;

            if (newmask & (1 << (m-1)))

                newmask -= (1 << (m-1));

            newmask = (newmask << 1);

            if (j == m)

                ans = min(ans, solve(i+1, 1, newmask) + 1);

            else

                ans = min(ans, solve(i, j+1, newmask) + 1);

        }

    }

    ready[i][j][mask] = true;

    dp[i][j][mask] = ans;

    return ans;

}

int main() {

    cin >> n >> m;

    grid.resize(n+1);

    for (int i = 1; i <= n; i++) {

        cin >> grid[i];

        grid[i] = "." + grid[i];

    }

    cout << solve(1, 1, 0) << '\n';

}