algorithm - 在某些限制条件下让人们就座的方式数量

Question

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

计算 k 人可以坐在 2 xn 矩阵中的方式数（n 和 k 是通过标准输入从用户那里获得的）。该矩阵也由用户给出，可以包含以下字符：'.' - 人们可以坐在这里，'#' - 人们不能坐在这里。

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

例如，如果 n = 3，k = 2 并给出以下矩阵：

..#
...

答案是 5。在矩阵中让 2 人坐下的所有可能方式是（u 表示一个人坐在那个场地上）：

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

标签： algorithmdynamic-programming

Answer 1

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

1. 用户处于最高位置
2. 用户在底部位置
3. 没有用户

因此，在每一步中，我们都可以从之前的状态转移，并且我们需要为每个状态和每个用户数量保留多种方式：

• 状态Top可以移动到状态：Bottom或None
• 状态Bottom可以移动到状态：Top或None
• 状态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;
}