[Baekjoon] 2048 (Easy)

Problema

E il gioco 2048 che tutti conoscono. Ma con vincoli aggiuntivi:

Un blocco che si e gia fuso in un movimento non puo fondersi di nuovo
Se 3 o piu blocchi possono fondersi, la fusione parte da quelli piu vicini alla direzione del movimento
- es., Se si muove verso l’alto, fondere prima quelli in alto

Soluzione

L’idea della fusione in se e semplice da trovare. Se vuoto, sposta il valore; se i valori sono uguali, raddoppia; altrimenti, posiziona nella cella sopra.

La parte difficile da capire, anche leggendo le spiegazioni di altri, era come impedire ai blocchi gia fusi di fondersi di nuovo. Mi aspettavo una qualche flag, ma l’approccio incrementa continuamente l’indice di riga o colonna per il target della fusione.

La seconda difficolta era gestire le quattro direzioni. Richiede una solida comprensione di cosa elaborare prima tra righe e colonne.

Per esempio, muovendosi a sinistra o destra, si itera per colonna e si sposta una riga alla volta. Per su o giu, si itera per riga e si sposta una colonna alla volta.

1
if direction == 0:
2
        # Guardare tutte le colonne di arr, quindi iterare n volte
3
        for j in range(n):
4
            idx = 0
5
            # Guardare tutte le righe tranne la 0-esima
6
            for i in range(1, n):
7
                # Se l'elemento non è 0 == non è vuoto
8
                if arr[i][j]:
9
                    # Salvare cosa stiamo per spostare
10
                    temp = arr[i][j]
11
                    # Svuotare la posizione originale
12
                    arr[i][j] = 0
13
                    # Se la destinazione è 0
14
                    if arr[idx][j] == 0:
15
                        # È vuota, quindi basta spostare
16
                        arr[idx][j] = temp
17
                    # Se ciò che spostiamo è uguale alla destinazione
18
                    elif arr[idx][j] == temp:
19
                        # Fondere
20
                        arr[idx][j] = temp * 2
21
                        # Incrementare idx per non fondere di nuovo
22
                        idx += 1
23
                    # Se ciò che spostiamo è diverso dalla destinazione
24
                    else:
25
                        idx += 1 # Bloccare
26
                        arr[idx][j] = temp # Ripristinare

[0, 3] sono mappati su, giu, sinistra, destra in ordine. direction = 0 significa che il codice sopra sposta i blocchi verso l’alto.

Spostare verso l’alto e semplice. Sinistra e destra sono piu complicati. Ecco lo spostamento a sinistra:

1
elif direction == 2:
2
        for i in range(n):
3
            idx = 0
4
            for j in range(1, n):
5
                if arr[i][j]:
6
                    # Salvare cosa stiamo per spostare
7
                    temp = arr[i][j]
8
                    # Svuotare la posizione originale
9
                    arr[i][j] = 0
10
                    # Se la destinazione è 0
11
                    if arr[i][idx] == 0:
12
                        # È vuota, quindi basta spostare
13
                        arr[i][idx] = temp
14
                    # Se ciò che spostiamo è uguale alla destinazione
15
                    elif arr[i][idx] == temp:
16
                        # Fondere
17
                        arr[i][idx] = temp * 2
18
                        # Incrementare idx per non fondere di nuovo
19
                        idx += 1
20
                    # Se ciò che spostiamo è diverso dalla destinazione
21
                    else:
22
                        idx += 1 # Bloccare
23
                        arr[i][idx] = temp # Ripristinare

Uso sempre i per la variabile riga e j per la variabile colonna. Per lo spostamento a sinistra, bisogna iterare per colonna e spostare una riga alla volta. Quindi l’ordine dei cicli va invertito per iterare prima i, poi j.

Il resto segue lo stesso pattern dello spostamento verso l’alto.

Per spostare verso il basso, si inverte il range per i; per spostare a destra, si inverte il range per j. Cioe, iterare da n-2 fino a 1.

Codice

https://github.com/naem1023/codingTest/blob/master/implementation/acmipic-12100.py