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 (row1, column) or at (row, column1)  notice that they can sit on (row1, column1)).
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

Let's go through
2 x N
matrix from left to right. On each column we could have only 3 states: User on top position
 User on bottom position
 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
orNone
 State
Bottom
can move to states:Top
orNone
 State
None
can move to states:Top
,Bottom
orNone
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; }