algorithm - 给定某些限制的座位方式的数量

Question

我正在努力解决这个问题，所以如果有人能提供帮助，我将不胜感激。问题是这样的:

在一个2×n的矩阵中计算k个人可以坐的方式数(n和k是通过标准输入从用户那里得到的)。矩阵也由用户提供，可以包含以下字符:'.' - 人们可以坐在这里，'#' - 人们不能坐在这里。

矩阵中的人不能相邻(也就是说，如果一个人位于(row，column)，另一个人不能坐在(row-1，column)或(row，column-1) - 注意他们可以坐在(第 1 行，第 1 列)上)。

例如，如果 n = 3，k = 2 并给定以下矩阵:

..#
...

答案是 5。在矩阵中让 2 人就座的所有可能方式是(u 表示一个人坐在那个 field 上):

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

Answer 1

让我们从左到右遍历 2 x N 矩阵。在每一列上我们只能有 3 个状态:

1. 用户排名靠前
2. 底部位置的用户
3. 没有用户

因此，在每一步中，我们都可以从以前的状态转移，我们只需要为每个状态和每个用户数量保留方法数:

• State Top 可以移动到状态:Bottom 或 None
• State Bottom 可以移动到状态:Top 或 None
• State None 可以移动到状态:Top、Bottom 或 None

答案是具有 K 个用户的所有状态的总和。

示例代码:

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