Solução Pilha de Dados

0 Flares Facebook 0 0 Flares ×

Solução por Rogério Júnior

Para ver o problema original, clique aqui.

 

O problema é uma função recursiva muito simples. O estado da recursão será a posição do dado da pilha que estamos olhando (onde o topo é 1) e e qual a face dele que está virada para cima (solve(pos,cima)), e ela retornará o maior valor de um lado da sub-pilha formada por este dados e os abaixo dele. Sabendo a face de cima de um dado, sabemos qual a de baixo pelo desenho. Chamaremos faces A, B, ..., F de faces 1, 2, ..., 6, onde dado[pos][i] guarda qual o número da face i no dado na posição pos.

Para um estado, percorreremos todas as faces que não são topo ou cima e usaremos a melhor para o lado da pilha que terá valor máximo. Chamaremos este valor de bestface. Se o dado olhado for o último, retornamos bestface. Olharemos o próximo dado, procurando qual de duas faces tem o mesmo valor da face de baixo do dado pos (seja ela new_cima), e chamaremos a recursão agora com esta sendo a face de cima (solve(pos+1,new_cima)).

No final, chamamos a recursão para cada uma das possíveis faces de cima do primeiro dado. Note que a melhor resposta da recursão para o primeiro dado soluciona o problema. Segue o código para melhor entendimento:

0 Flares Facebook 0 0 Flares ×
0 Flares Facebook 0 0 Flares ×
%d bloggers like this: