La Formiga de Langton P41098

La Formiga de Langton viu en una regió $n \times n$, amb $n$ senar. La formiga té una llista d’$m$ colors $c_0, \ldots c_{m - 1}$, i d’$m$ girs asociats $g_0, \ldots 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_0$.

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_0$ i $g_n = g_0$. 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 \le k \le 2 \cdot 10^6$, $2 \le m \le 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_0 =$ ‘Beige’, $g_0 =$ ‘D’, $c_1 =$ ‘Red’ i $g_1 =$ ‘E’.

• Cas B:   Casos de tot tipus.