PKU 2384 - Harder Sokoban Problem

Autor da análise: gabrielrcpgabrielrcp

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=2384

Resumo

Dado um tabuleiro de sokoban $N \times N$, $2 \leq N \leq 25$ calcular a posicao inicial do jogador e do bloco de modo a maximizar o numero de jogadas necessarias para que se termine o jogo. Deve ser possível vencer sempre.

Solução

Pense num grafo (ímplicito) ao jogo. Os vértices desse grafo são um par ordenado (posicao_do_jogador, posicao_do_bloco) e dois vertices são adjacentes se pudermos, através de um movimento, mudar de um estado para outro. Assim temos no máximo $N^4$ vértices e $5 N^4$ arestas.

O que queremos saber é qual o vértice que tem a máxima distância mínima para o conjunto dos vértices em que posicao_do_bloco é a posição final que ele deve ficar.

Para fazer isso, podemos rodar uma BFS no grafo inverso, partindo de todos os estados em que o jogo já está resolvido. A resposta é o quão longe conseguimos chegar nessa BFS.

O grafo invertido pode ser ímplicito, nele podemos movimentar o jogador sem mudar o bloco ou puxar o bloco.

Testes

Entrada

Saída

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License