Combine o algoritmo de pesquisa de pares?

Question

Eu encontrei um jogo de combinação de pares interessantes em http://xepthu.uhm.vn. A regra é simples, você precisa encontrar e conectar dois Pokemon idênticos, mas o caminho entre eles não está bloqueado e a direção não pode ser alterada 3 vezes. Vamos ver um exemplo:

Penso muito sobre o algoritmo para verificar se o caminho entre 2 Pokemon selecionado é válido, mas porque sou um novato, por isso não consigo encontrar nenhuma solução. Você pode me sugerir um em C#?

Answer 1

This is basically a path finding problem from graph theory. The fields in the grid are the nodes, and all adjacent fields are connected by an edge.

Path finding is a well-known problem, and there are many algorithms that solve this. Since your graph is quite small, the best solution here is probably just a brute force algorithm. A popular path finding algorithm is Dijkstra's algorithm.

---

Brute force: Start at some pokemon and explore all possible ways to see if one leads to an identical pokemon. You can stop exploring a way if the way is blocked or has more than 2 turns.

You'll need some "pointer" pointing to a field in the grid. The pointer can move left, right, up or down, provided that the field in that direction is not blocked. Move the pointer to an adjacent field. Remember where you came from and how many turns you made. Repeat this until you've reached your destination. Backtrack if the number of turns reaches 3. Make sure you don't run in circles.

Answer 2

Dê uma olhada nos gráficos planares. Você precisará introduzir uma segunda condição: não mais que quatro nós podem ser percorridos (Nó Iniciar - Alteração da Primeira direção - Alteração da segunda direção - Nó final).