Enganxat als videojocs P22716

Els videojocs formen una part indispensable del dia a dia d’en Noldo. Tant és així, que fins i tot és capaç de postposar la presentació del seu projecte de fi de carrera per passar una bona estona jugant. En aquest problema haureu de resoldre el videojoc al qual va estar jugant en Noldo el dia que hauria d’haver estat defensant el seu projecte.

Cal travessar una graella rectangular des d’una posició inicial fins a una posició final en el mínim temps possible. Cada casella té una sala o un obstacle. No es pot passar pels obstacles, ni sortir fora de la graella. Cada sala té una única porta de sortida, orientada inicialment al nord, est, sud o oest. Després de cada unitat de temps, totes les portes es mouen 90 graus en sentit horari (per exemple, una porta orientada a l’est, després ho estarà al sud, després a l’oest, etcètera). Quan s’està en una sala, es pot optar per esperar una unitat de temps, o bé desplaçar-se a la sala adjacent per la porta de sortida, gastant també una unitat de temps.

Entrada

L’entrada comença amb el nombre de casos de prova. Cada cas comença amb el nombre de files $1 \le n \le 500$ i de columnes $1 \le m \le 500$ del mapa. Les $n$ línies següents contenen cadascuna els $m$ caràcters d’una fila, amb la convenció següent:

• ‘I’: sala inicial, orientada cap al nord.

• ‘F’: sala final.

• ‘X’: casella bloquejada per un obstacle.

• ‘N’: sala orientada inicialment cap al nord.

• ‘E’: sala orientada inicialment cap a l’est.

• ‘S’: sala orientada inicialment cap al sud.

• ‘W’: sala orientada inicialment cap a l’oest.

Cada graella tindrà exactament una ‘I’ i una ‘F’.

Sortida

Per a cada mapa donat, escriviu el número de cas, seguit del temps mínim necessari per anar de l’origen al destí. Si no és possible, cal indicar-ho. Seguiu el format de l’exemple.