Recorregut de cavall P45871

Un cavall dels escacs es troba en un tauler $n \times 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^4$.

Observacions

• Recomanem resoldre aquest problema en C++.

• La solució esperada és una senzilla força bruta.