Enganxat als videojocs P22716


Statement
 

pdf   zip

thehtml

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.

[r]

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 ≤ n ≤ 500 i de columnes 1 ≤ m ≤ 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.

Public test cases
  • Input

    8
    
    4 4
    XXXX
    XFSX
    XINX
    XXXX
    
    2 1
    I
    F
    
    2 2
    IE
    XF
    
    2 2
    IE
    SF
    
    1 3
    FWI
    
    1 3
    FNI
    
    4 5
    XXXXX
    XNXFX
    XIXSX
    XXXXX
    
    4 7
    NSEWSNE
    EESWNWI
    SSNNEEW
    FSEWNSW
    

    Output

    #1: 1
    #2: 3
    #3: 6
    #4: 4
    #5: 5
    #6: 8
    #7: impossible
    #8: 14
    
  • Information
    Author
    Jaher
    Language
    Catalan
    Other languages
    English
    Official solutions
    C++
    User solutions
    C++