Number of ways to seat people given certain constraints

I'm struggling with this problem so if anyone can help, that would be appreciated. The problem goes like this:

Calculate the number of ways that k people can sit in a 2 x n matrix (n and k are obtained from the user through standard input). The matrix is also given by the user and can contain the following characters: '.' - people can sit here, '#' - people can't sit here.

People in the matrix can't be adjacent (that is if one person is situated at (row, column), another person can't sit at (row-1, column) or at (row, column-1) - notice that they can sit on (row-1, column-1)).

For example, if n = 3, k = 2 and given the following matrix:

..#
...

the answer would be 5. All possible ways to seat 2 people in the matrix are (u means that a person is sitting on that field):

u.#   .u#   ..#   u.#   .u#
.u.   u..   u.u   ..u   ..u

1 answer

  • answered 2018-11-08 09:28 Kozyr

    Let's go through 2 x N matrix from left to right. On each column we could have only 3 states:

    1. User on top position
    2. User on bottom position
    3. No users

    So, on each step we could move from previous states and all we need to keep number of ways for each state and each number of users:

    • State Top can move to states: Bottom or None
    • State Bottom can move to states: Top or None
    • State None can move to states: Top, Bottom or None

    Answer is a sum of all states with K users.

    Sample code:

    #include <iostream>
    #include <map>
    #include <string>
    using namespace std;
    
    enum State: int
    {
        Top,    // u
                // -
    
        Bottom, // -
                // u
    
        None,   // -
                // -
    };
    
    int main()
    {
        int N, K; cin >> N >> K;
        string S[2]; cin >> S[0] >> S[1];
    
        map<State, map<int, int>> prev = { { None, {{0,1}} } };
        for (int i = 0; i < N; ++i) {
            map<State, map<int, int>> cur;
    
            if (S[0][i] == '.') {
                for (auto& w : prev[None])   cur[Top][w.first + 1] += w.second;
                for (auto& w : prev[Bottom]) cur[Top][w.first + 1] += w.second;
            }
            if (S[1][i] == '.') {
                for (auto& w : prev[None]) cur[Bottom][w.first + 1] += w.second;
                for (auto& w : prev[Top])  cur[Bottom][w.first + 1] += w.second;
            }
            for (auto& w : prev[None])   cur[None][w.first] += w.second;
            for (auto& w : prev[Top])    cur[None][w.first] += w.second;
            for (auto& w : prev[Bottom]) cur[None][w.first] += w.second;
    
            swap(cur, prev);
        }
    
        cout << (prev[Top][K] + prev[Bottom][K] + prev[None][K]) << endl;
        return 0;
    }