La Formiga de Langton P41098

Graphic problem

La Formiga de Langton viu en una regió n × n, amb n senar. La formiga té una llista d’m colors c₀, … c_{m − 1}, i d’m girs asociats g₀, … g_{m − 1}, que poden ser ‘D’ o ‘E’ (90 graus a la dreta o a l’esquerra). Al principi, cada quadrat està pintat de color c₀.

Inicialment, la formiga es troba al quadrat central, mirant cap amunt. La formiga es mou així: Repetidament, si la casella on està és de color c_i, la pintarà de color c_{i + 1}, girarà segons indiqui g_{i + 1}, i es mourà una casella endavant segons la nova direcció cap a on miri. Els índexs són cíclics, és a dir, c_n = c₀ i g_n = g₀. Podríeu dibuixar els colors de les caselles del mapa després de k iteracions?

Entrada

L’entrada comença amb els enters n, k, i m, seguits d’m parells c_i g_i, tot en línies diferents. Assumiu que n és senar i no més gran que 500, 1 ≤ k ≤ 2 · 10⁶, 2 ≤ m ≤ 20, que tots els colors són diferents, i que la formiga mai sortirà de la quadrícula.

Sortida

Genereu una imatge de mida (n, n) amb l’estat de la quadrícula després de k iteracions.

Puntuació

• Cas A:   Casos amb m = 2, c₀ = ‘Beige’, g₀ = ‘D’, c₁ = ‘Red’ i g₁ = ‘E’.  50% Punts 

• Cas B:   Casos de tot tipus.  50% Punts