Attacking Rooks - UVA 12668

A abordagem mais natural para resolver esse problema seria via backtracking.

Entretanto, o tabuleiro pode ser 100X100. Com isso, teríamos 10.000 casas.

Com backtracking, em cada casa, teríamos que decidir se colocaríamos uma torre

ou não. Ou seja, duas decisões. De tal forma que teríamos 2^10000 decisões.Só pra você ter

uma ideia de quão grande é esse número. Supondo que o seu computador execute 100.000 instruções

em um segundo, usar backtracking levaria aproximadamente 6 × 10^2991 milhões de anos.

:-)

Para resolver, vamos primeiro pensar em um caso mais simples, sem os peões e depois vamos mostrar como resolver considerando os peões.

Imagine que temos um tabuleiro vazio, sem os peões.

Nesse caso, poderíamos simplesmente colocar todas as torres nas diagnonais para obter uma resposta.

Porém, vamos pensar em outra solução.

Vamos colocar uma torre na posição (1,2):

Com essa configuração, não é mais possível colocar nenhuma torre na linha 1 e nem na coluna 2.

Podemos enxergar esse problema como sendo um problema de match de um grafo bipartido, onde escolhemos as arestas onde cada vértice é selecionado apenas uma vez. De um lado teríamos os vértices representando as linhas, e do outro os vértices representando as colunas. E arestas conectando todos eles.

Assim, ao colocarmos uma torre na posição (1,2), estamos na verdade selecionando a aresta que conecta o vértice verde 1 com o vértice amarelo 2:

Assim, a solução para essa versão do problema é um match perfeito, ou seja, todas as arestas verdes conectadas a uma aresta amarela diferente, como por exemplo:

Podemos ver esse problema como um problema de fluxo máximo e então utilizar o algoritmo de Ford Fulkerson para resolvê-lo. A grande vantagem de fazer isso é poder reduzir a complexidade do problema para O(arestas * fluxo máximo). Para isso, precisamos adicionar os nós de origem e de destino, chamados aqui de source e sink, respectivamente.

Além disso, considere que todas as arestas têm capacidade 1. Assim, o problema passa a ser encontrar o caminho de fluxo máximo. Perceba que as existem 4 arestas de entrada nas linhas, ou seja, cada vértice de linha receberá 1 como entrada de fluxo. A mesma coisa ocorre entre os vértices das colunas e o sink. Assim, o fluxo máximo possível será 4.

E os peões? :-)

Vamos aplicar a mesma ideia do grafo bipartido. Só que vamos usar os peões para definir ondem as linhas são quebradas e onde as colunas são quebradas. Suponha o tabuleiro abaixo:

Nele existem 3 peões. O peão da posição (0,1) quebra a linha 0 em duas partes e elimina a casa (0,1) como local de colocar uma torre. Ou seja, agora, mesmo que tenha uma torre na posição (0, 0), seria possível colocar outra torre na posição (0,2), porque o peão (0,1) ficou no meio das duas. Ou seja, escolher a linha 0 não elimina a linha inteira como possibilidade. Mas escolher colocar a torre na posição (0,2), elimina todo o espaço entre o peão (0,1) e o final da matriz.

Na versão sem peões, representamos cada linha por um vértice. Agora, vamos representar os intervalos formados pelos peões em cada linha como se fosse um vértice. Faremos a mesma coisa com as colunas.

Dividindo a matriz de acordo com as divisões feitas nas linhas, obtemos:

Ou seja, temos um total de 6 vértices, sendo cada cor representando um vértice.

E fazendo a mesma coisa com as colunas, obtemos:

Também um total de 6 vértices (nem sempre esses números são iguais).

Agora faça uma interseção entre esses vértices para traçar as arestas.

Mais uma vez, cada aresta tem capacidade de 1. Perceba que interessante, se você colocar por exemplo uma torre na posição (2,3). Significa que você colocou "ativou" a aresta entre o componente roxo e o componente verde escuro. Com isso, você não poderá utilizar mais a aresta entre o componente amarelo e o verde escuro, nem entre o roxo e o roxo claro.

Assim, o fluxo máximo desse grafo será exatamente igual a quantidade de torres que você conseguirá colocar.