Recorregut de cavall P45871

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 10⁴.

Observacions

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