domingo, agosto 07, 2011

Minha solução ao "desafio" do Raul

Num post anterior coloquei um problema envolvendo xadrez e programação passado por um amigo, segue aqui a melhor solução que consegui (e com uma ajudinha do CLRS tenho que confessar :-) )

Pra quem não tem o go instalado na máquina, pode rodar o código em http://golang.org

package main

import "fmt"

func criaTabela(N int) [][][]int64{
 T := make([][][]int64, 2)//pos atual e anterior.
 for t:= range T {
  T[t] = make([][]int64,N)
  for t2:= range T[t] {
   T[t][t2] = make([]int64,N)
  }
 }
 return T
}

func Solução(N, M, xi, yi, xf, yf int) int64 {
 T := criaTabela(N,M)
 // Posição inicial
 T[0][xi][yi] = 1 
 // Movimentos do cavalo.
 C  := [8][2]int{{2,1},{2,-1},{-2,1},{-2,-1},{1,2},{-1,2},{1,-2},{-1,-2}}
 // Percorre todo o tabuleiro para todos os movimentos e todos os lances possíveis.
 atual,anterior := 1, 0
 for i:=0; i < M; i++ {
  for x:=0; x < N; x++{
   for y:=0; y < N; y++{
    T[atual][x][y] = 0
    for m:=0; m < len(C); m++ {
     if x+C[m][0] >= 0 && x+C[m][0] < N && //Não ultrapassa bordas do tabuleiro? 
        y+C[m][1] >= 0 && y+C[m][1] < N {  // então soma de movimentos anteriores.
          T[atual][x][y] += T[anterior][x+C[m][0]][y+C[m][1]]
        }
    } 
   }
  }
  atual, anterior = anterior, atual
 } 
 return T[anterior][xf][yf]
}

func main(){
 fmt.Println("Solução:",Solução(3,1,0,0,2,1)); // Vai: 1
 fmt.Println("Solução:",Solução(3,2,0,0,0,0)); // Vai e volta: 2
 fmt.Println("Solução:",Solução(3,2,0,0,2,1)); // Impossível:  0
 fmt.Println("Solução:",Solução(100,50,0,0,0,98)); //Número beeeem grande...
}