Normalmente ho un approccio molto intuitivo a un algoritmo efficiente. In sostanza, so qual è il collo di bottiglia e come posso migliorare l'algoritmo. Tuttavia, ora sono bloccato e ho bisogno di qualche "ispirazione".
Il problema
L'idea stessa è molto semplice. Ho una matrice di n x m booleani. Inserisco un'altra griglia, anche di n x m booleani. La domanda che questo algoritmo deve risolvere è se la forma di input può mai essere abbinata alla forma di output: ciò può essere fatto specchiando, ruotando e spostando la forma di input intorno. Ho solo bisogno di sapere se le due forme possono essere abbinate o meno: le trasformazioni attuali non contano.
Esempi:
Forma del bersaglio:
0 0 0
0 1 1
0 0 0
Input:
1 0 0
1 0 0
0 0 0
Chiaramente, questo può essere fatto. La trasformazione è semplice:
1) Ruota in senso antiorario:
0 1 1
0 0 0
0 0 0
2) Sposta giù:
0 0 0
0 1 1
0 0 0
Un controllo rapido può essere fatto facilmente: conta quanti zeri o quanti sono nella matrice di input. Se questo non corrisponde al numero di zeri e quelli nella forma di destinazione, non è possibile creare la forma di destinazione.
Una domanda più ampia e generale sarebbe quale specifica classe di algoritmo sto cercando. Per me non è chiaro, anche se usando il mio esempio, direi che un algoritmo di path-path costruito con cura potrebbe funzionare.
Voglio anche sottolineare che non sono uno studente di informatica, la programmazione è uno dei miei hobby. Ho una corretta comprensione delle "manipolazioni di matrice di base" - forse c'è un meraviglioso "trucco matematico" per questo.