Recorregut de cavall P45871


Statement
 

pdf   zip

thehtml

Un cavall dels escacs es troba en un tauler n × m on hi ha algunes caselles prohibides. De quantes maneres pot visitar totes les altres caselles exactament una vegada?

Entrada

L’entrada consisteix en diversos casos, cadascun amb n i m, seguit d’n línies amb m caràcters cadascuna. Les ‘X’ indiquen obstacles, els punts caselles lliures, i una ‘I’ la posició inicial del cavall. Podeu suposar que n i m es troben entre 2 i 8.

Sortida

Per a cada cas, escriviu el nombre de maneres de visitar totes les caselles lliures exactament un cop. Amb els jocs de proves donats, aquest nombre sempre estarà entre 1 i 104.

Observacions

  • Recomanem resoldre aquest problema en C++.
  • La solució esperada és una senzilla força bruta.
Public test cases
  • Input

    2 3
    XX.
    IXX
    
    3 4
    I..X
    .XX.
    X..X
    
    5 4
    X..X
    ....
    .I..
    X...
    X.X.
    
    

    Output

    1
    2
    40
    
  • Information
    Author
    Xavier Povill
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++