Várias maneiras de acomodar as pessoas dadas certas restrições

votos
1

Eu estou lutando com este problema por isso, se alguém puder ajudar, que seria apreciada. O problema é o seguinte:

Calcular o número de maneiras que k pessoas pode sentar-se em uma matriz de 2 x n (n e k são obtidos a partir do utilizador através da entrada padrão). A matriz também é dado pelo utilizador e pode conter os seguintes caracteres: '' - as pessoas podem sentar aqui, '#' - as pessoas não podem se sentar aqui.

Pessoas na matriz não pode ser adjacente (isto é, se uma pessoa está situado em (linha, coluna), outra pessoa não pode sentar-se em (linha-1, coluna) ou em (linha, coluna 1) - que aviso eles podem sentar-se no (row-1, coluna 1)).

Por exemplo, se n = 3, k = 2 e tendo em conta a seguinte matriz:

..#
...

a resposta seria 5. maneiras todo o possível para acomodar 2 pessoas na matriz são (u significa que uma pessoa está sentada nesse campo):

u.#   .u#   ..#   u.#   .u#
.u.   u..   u.u   ..u   ..u
Publicado 08/11/2018 em 06:33
fonte usuário
Em outras línguas...                            


1 respostas

votos
0

Vamos passar por 2 x Nmatriz da esquerda para a direita. Em cada coluna poderíamos ter apenas 3 estados:

  1. Usuário em posição superior
  2. Usuário em posição inferior
  3. não há usuários

Assim, em cada passo que poderia passar de estados anteriores e tudo o que precisamos para manter número de maneiras para cada estado e cada número de usuários:

  • Estado Toppode mover-se para estados: BottomouNone
  • Estado Bottompode mover-se para estados: TopouNone
  • Estado Nonepode mover-se para estados: Top, BottomouNone

Resposta é uma soma de todos os estados com Kos usuários.

Código de amostra:

#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;
}
Respondeu 08/11/2018 em 09:28
fonte usuário

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more