Jogos em grafos arbitrários

Deixe um jogo ser jogado por dois jogadores em um grafo arbitrário $G$. Ou seja, o estado atual do jogo é um certo vértice. Os jogadores realizam movimentos por turnos e passam do vértice atual para um vértice adjacente usando uma aresta de conexão. Dependendo do jogo, a pessoa que não puder se mover perderá ou vencerá o jogo.

Consideramos o caso mais geral, o caso de um grafo(arbitrário) direcionado com ciclos. É nossa tarefa determinar, dado um estado inicial, quem vencerá o jogo se ambos os jogadores jogarem com estratégias ideais ou se o resultado do jogo será um empate.

Vamos resolver esse problema com muita eficiência. Encontraremos a solução para todos os possíveis vértices iniciais do grafo em tempo linear em relação ao número de arestas: $O(m)$.

Descrição do algoritmo

Vamos chamar um vértice de vértice vencedor, se o jogador que iniciar neste estado vencer o jogo, se jogar da melhor maneira possível (independentemente do turno do outro jogador). Da mesma forma, chamaremos um vértice de vértice perdedor, se o jogador que iniciar nesse vértice perder o jogo, se o oponente jogar da melhor maneira.

Para alguns dos vértices do grafo, já sabemos com antecedência se eles são vértices vencedores ou perdedores: ou seja, todos os vértices que não têm arestas de saída.

Também temos as seguintes regras:

Assim, podemos definir um algoritmo que é executado em $O(n m)$ imediatamente. Analisamos todos os vértices e tentamos aplicar a primeira ou a segunda regra e repetimos.

No entanto, podemos acelerar esse procedimento e reduzir a complexidade para $O(m)$.

Analisaremos todos os vértices, para os quais sabemos inicialmente se eles são estados vencedores ou perdedores. Para cada um deles, iniciamos uma DFS. Essa DFS retornará pelas arestas invertidas. Primeiro de tudo, ela não entrará em vértices que já estão definidos como vértices vencedores ou perdedores. E posteriormente, se a pesquisa passar de um vértice perdedor para um vértice indefinido, marcamos ele(indefinido) como vértice vencedor e continuamos a DFS usando esse novo vértice. Se passarmos de um vértice vencedor para um vértice indefinido, devemos verificar se todas as arestas deste levam a vértices vencedores. Podemos realizar esse teste em $O(1)$ armazenando o número de arestas que levam a um vértice vencedor para cada vértice. Portanto, se passarmos de um vértice vencedor para um indefinido, aumentamos o contador e verificamos se esse número é igual ao número de arestas de saída. Se for esse o caso, podemos marcar esse vértice como um vértice perdedor e continuar a DFS nesse vértice. Caso contrário, ainda não sabemos se esse vértice é um vértice vencedor ou perdedor e, portanto, não faz sentido continuar a DFS usando ele.

No total, visitamos todos os vértices vencedores e perdedores exatamente uma vez (vértices indefinidos não são visitados) e passamos por cada aresta também no máximo uma vez. Portanto, a complexidade é $O(m)$.

Implementação

Aqui está a implementação dessa DFS. Assumimos que a variável adj_rev armazena a lista de adjacência do grafo na forma reversa, ou seja, em vez de armazenar a aresta $(i, j)$ do grafo, ela armazena: $(j, i)$. Também para cada vértice, assumimos que o grau de saída já foi calculado.

vector<vector<int>> adj_rev;

vector<bool> winning;
vector<bool> losing;
vector<bool> visited;
vector<int> degree;

void dfs(int v) {
    visited[v] = true;
    for (int u : adj_rev[v]) {
        if (!visited[u]) {
            if (losing[v])
                winning[u] = true;
            else if (--degree[u] == 0)
                losing[u] = true;
            else
                continue;
            dfs(u);
        }
    }
}

Exemplo: "Policial e ladrão"

Aqui está um exemplo concreto desse jogo.

Há um tabuleiro(ou grid) $m \times n$. Algumas das células não podem ser entradas. As coordenadas iniciais do policial e do ladrão são conhecidas. Uma das células é a saída. Se o policial e o ladrão estiverem localizados na mesma célula a qualquer momento, o policial vence. Se o ladrão estiver na cela de saída (sem o policial também estar na cela), o ladrão vence. O policial pode andar em todas as 8 direções, o ladrão apenas em 4 (ao longo do eixo de coordenadas). O policial e o ladrão revezam-se em turnos de movimento. No entanto, eles também podem pular um turno, se quiserem. A primeira jogada é feita pelo policial.

Vamos agora construir o grafo. Para isso, devemos formalizar as regras do jogo. O estado atual do jogo é determinado pelas coordenadas do policial $P$, pelas coordenadas do ladrão $T$, e também por quem é a vez, vamos chamar essa variável de $P_{\text{turno}}$ (o que é verdade(true) quando é a vez do policial). Portanto, um vértice do grafo é determinado pelo triplo $(P, T, P_{\text{turno}})$ O grafo então pode ser facilmente construído, simplesmente seguindo as regras do jogo.

Em seguida, precisamos determinar quais vértices estão ganhando e quais estão perdendo inicialmente. Há um ponto sutil aqui. Os vértices vencedores / perdedores dependem, além das coordenadas, também de $P_{\text{turno}}$ - de quem é o turno de jogada. Se for a vez do policial, o vértice é um vértice vencedor, se as coordenadas do policial e do ladrão coincidirem, e o vértice é um perdedor se não for um vencedor e o ladrão estiver no vértice de saída. Se for a vez do ladrão, então um vértice é um vértice perdedor se as coordenadas dos dois jogadores coincidirem e, é um vértice vencedor se não for um perdedor e o ladrão está no vértice de saída.

O único ponto antes da implementação é que você precisa decidir se deseja criar o grafo explicitamente ou apenas construí-lo dinamicamente(durante as jogadas). Por um lado, criar o grafo explicitamente será muito mais fácil e há menos chances de cometer erros. Por outro lado, aumentará a quantidade de código e o tempo de execução será mais lento do que se você criar o grafo dinamicamente.

A implementação a seguir construirá o grafo explicitamente:

struct State {
    int P, T;
    bool Pstep;
};

vector<State> adj_rev[100][100][2]; // [P][T][Pturno]
bool winning[100][100][2];
bool losing[100][100][2];
bool visited[100][100][2];
int degree[100][100][2];

void dfs(State v) {
    visited[v.P][v.T][v.Pstep] = true;
    for (State u : adj_rev[v.P][v.T][v.Pstep]) {
        if (!visited[u.P][u.T][u.Pstep]) {
            if (losing[v.P][v.T][v.Pstep])
                winning[u.P][u.T][u.Pstep] = true;
            else if (--degree[u.P][u.T][u.Pstep] == 0)
                losing[u.P][u.T][u.Pstep] = true;
            else
                continue;
            dfs(u);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];

    for (int P = 0; P < n*m; P++) {
        for (int T = 0; T < n*m; T++) {
            for (int Pstep = 0; Pstep <= 1; Pstep++) {
                int Px = P/m, Py = P%m, Tx = T/m, Ty = T%m;
                if (a[Px][Py]=='*' || a[Tx][Ty]=='*')
                    continue;

                bool& win = winning[P][T][Pstep];
                bool& lose = losing[P][T][Pstep];
                if (Pstep) {
                    win = Px==Tx && Py==Ty;
                    lose = !win && a[Tx][Ty] == 'E';
                } else {
                    lose = Px==Tx && Py==Ty;
                    win = !lose && a[Tx][Ty] == 'E';
                }
                if (win || lose)
                    continue;

                State st = {P,T,!Pstep};
                adj_rev[P][T][Pstep].push_back(st);
                st.Pstep = Pstep;
                degree[P][T][Pstep]++;
                     
                const int dx[] = {-1, 0, 1, 0, -1, -1, 1, 1};   //movimentação pelo grid / grafo
                const int dy[] = {0, 1, 0, -1, -1, 1, -1, 1};  
                for (int d = 0; d < (Pstep ? 8 : 4); d++) {
                    int PPx = Px, PPy = Py, TTx = Tx, TTy = Ty;
                    if (Pstep) {
                        PPx += dx[d];
                        PPy += dy[d];
                    } else {
                        TTx += dx[d];
                        TTy += dy[d];
                    }

                    if (PPx >= 0 && PPx < n && PPy >= 0 && PPy < m && a[PPx][PPy] != '*' &&
                        TTx >= 0 && TTx < n && TTy >= 0 && TTy < m && a[TTx][TTy] != '*')
                    {
                        adj_rev[PPx*m+PPy][TTx*m+TTy][!Pstep].push_back(st);
                        ++degree[P][T][Pstep];
                    }
                }
            }
        }
    }

    for (int P = 0; P < n*m; P++) {
        for (int T = 0; T < n*m; T++) {
            for (int Pstep = 0; Pstep <= 1; Pstep++) {
                if ((winning[P][T][Pstep] || losing[P][T][Pstep]) && !visited[P][T][Pstep])
                    dfs({P, T, (bool)Pstep});
            }
        }
    }

    int P_st, T_st;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 'P')
                P_st = i*m+j;
            else if (a[i][j] == 'T')
                T_st = i*m+j;
        }
    }

    if (winning[P_st][T_st][true]) {
        cout << "Policial pegou o ladrão"  << endl;
    } else if (losing[P_st][T_st][true]) {
        cout << "Ladrão escapa" << endl;
    } else {
        cout << "Empate" << endl;
    }
}