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:- 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; }