Bestimmen Sie bei zwei zusammenhängenden Formen desselben Bereichs den optimalen Weg, um die erste Form in eine minimale Anzahl zusammenhängender Segmente zu unterteilen, sodass sie neu angeordnet werden können, um die zweite Form zu bilden. Mit anderen Worten, ermitteln Sie die Mindestanzahl der erforderlichen Segmente, die beide Formen bilden können.

"Zusammenhängend" bedeutet, dass jedes Quadrat in der Form von jedem anderen Quadrat aus erreicht werden kann, indem man über Kanten geht. Formen und Segmente dürfen Löcher haben.

"Neu anordnen" bedeutet, dass Sie die Segmente verschieben. Sie können sie übersetzen, drehen und reflektieren.

Die Formen sind in einem Raster enthalten. Mit anderen Worten, jede Form besteht aus einer Sammlung von Einheitsquadraten, die durch ihre Ecken / Kanten verbunden sind.

Eingabespezifikationen

Die Eingabe wird in einem angemessenen Format bereitgestellt - Liste der Punkte, Array von Zeichenfolgen, die jedes Raster darstellen usw. Auf Anfrage können Sie auch die Größe des Rasters übernehmen. Die Gitter haben die gleichen Abmessungen und die beiden Formen haben garantiert die gleiche Fläche, und die Fläche ist positiv.

Ausgabespezifikationen

Die Ausgabe sollte nur eine einzelne positive Ganzzahl sein. Beachten Sie, dass es immer eine positive Antwort gibt, da Sie im schlimmsten Fall die Formen einfach in NEinheitsquadrate unterteilen.

Beispiele

Die Beispiele werden als Raster .dargestellt, wobei ein Leerzeichen und ein #Teil der Form dargestellt werden.

Fall 1

Eingang

.....
.###.
.#.#.
.###.
.....

###..
..#..
..#..
..###
.....

Ausgabe

2

Erläuterung

Sie können es in zwei L-förmige 4er-Blöcke unterteilen:

#
###

Fall 2

Eingang

#...
##..
.#..
.##.

.##.
####
....
....

Ausgabe

2

Erläuterung

Sie können die Formen folgendermaßen aufteilen:

A...
AA..
.A.
.BB.

.AA.
BBAA
....
....

Sie könnten auch tun:

A...
AA..
.B..
.BB.

.AB.
AABB
....
....

Fall 3

Eingang

#....#
######

.####.
.####.

Ausgabe

2

Erläuterung

A....B
AAABBB

.ABBB.
.AAAB.

(Dieser Testfall zeigt die Notwendigkeit, Formen für eine optimale Ausgabe zu drehen / reflektieren.)

Fall 4

Eingang

.###.
..#..

.##..
.##..

Ausgabe

2

Erläuterung

Unabhängig davon, wie Sie Blöcke auswählen, verhindert die Auswahl eines 2x1 aus der ersten Form zwangsläufig, dass die beiden anderen zusammen gruppiert werden. Somit können Sie eine 2x1 und zwei 1x1 verwenden. Allerdings (danke @Jonah) können Sie es in eine 3-Block-L-Form und ein einzelnes Quadrat wie folgt aufteilen:

.AAB.
..A..

.AA..
.BA..

Python 3.6 , 799 791 Bytes

7 Bytes gespeichert von Jonathan Frech und motavica

B=frozenset
M=min
X={}
T=lambda s:((x,y)for y,x in s)
N=lambda s:B((x-M(s)[0],y-M(T(s))[0])for x,y in s)
G=lambda s:{(x,y):s&{(x-1,y),(x+1,y),(x,y-1),(x,y+1)}for(x,y)in s}
C=lambda g,s,i=0:i<=len(g)and(len(g)==len(s)or C(g,s.union(*map(g.get,s)),i+1))
F=lambda s:N([(-x,y)for x,y in s])
P=lambda s,i=4:M([N(s),F(s),P(F(T(s)),i-1)],key=list)if i else s
S=lambda s,t=B(),i=0:t|S(s,B().union(u|{p}for u in t for p in s-u if C(G(u|{p}),{p}))if i else B([B([next(iter(s))])]),i+1)if-~i<len(s)else t
def U(s):
 k=P(s)
 if k in X:return
 j=[t for t in S(k)if C(G(k-t),{next(iter(k-t))})];X[k]={P(t):B()for t in j}
 for t in j:X[k][P(t)]|=B([B(P(k-t))]);U(t);U(k-t)
V=lambda s,t:1+M(V(v,w)for u in B(X[s])&B(X[t])for v in X[s][u]for w in X[t][u])if s^t else 1
A=lambda s,t:U(s)or U(t)or V(P(s),P(t))

Probieren Sie es online aus!

Verwendungszweck

A(s, t)nimmt zwei Formen an, wobei jede Form durch eine Liste von x, yGitterpositionen gegeben ist.

Eine Hilfsfunktion zum Konvertieren der grafischen Darstellung in eine Liste von Positionen finden Sie unten:

def H(g):
 g=g.split("\n")
 return[(x,y)for x in range(len(g[0]))for y in range(len(g))if"#"==g[y][x]]

Beispiel:

case1_1 = \
""".....
.###.
.#.#.
.###.
....."""

case1_2 = \
"""###..
..#..
..#..
..###
....."""

print(A(H(case1_1), H(case1_2))) # Prints 2

Erläuterung

Der hier verwendete Algorithmus ist etwas besser als Brute Force durch Zwischenspeichern von Unterformen. Für eine bestimmte Form werden alle Möglichkeiten zwischengespeichert, um diese Form in zwei zusammenhängende Formen aufzuteilen. Anschließend normalisiere ich diese Formen (verschiebe die Koordinaten so, dass sie am Ursprung beginnen, und finde dann eine Drehung / Reflexion davon, die im Cache verwendet wird). und speichern Sie sie im Cache, um später schnell nachzuschlagen. Bei allen Unterformen werden dann auch ihre Unterformen zwischengespeichert, bis die Einzelblockform erreicht ist.

Diese Unterformen werden generiert, indem sie in eine Diagramm-Adjazenzliste konvertiert und mithilfe eines BFS alle Untergraphen generiert werden. Wir können diese Untergraphen dann nach solchen filtern, bei denen die nicht enthaltenen Scheitelpunkte eine verbundene Komponente sind. Das Bestimmen, ob das Diagramm verbunden ist, erfolgt mit einem anderen BFS.

Nachdem der Cache vollständig ist, wird die Lösung gefunden, indem die beiden Formen verglichen werden, um die gemeinsamen Unterformen zu finden. Sobald diese Liste von Unterformen vorhanden ist, wird das nach dem Entfernen der gemeinsamen Form verbleibende Paar von Unterformen verwendet und derselbe Algorithmus erneut rekursiv angewendet, um die Mindestanzahl von Blöcken zu ermitteln, die zur Rekonstruktion der Form erforderlich sind. Dies gibt dann die Unterform mit dem Minimum all dieser Werte zurück und wir haben unsere Lösung.

Ich habe unten eine kommentierte Version eingefügt, um zu erklären, was jede Zeile tut.

B=frozenset
M=min
# Shapes are stored as a frozenset of tuples where each tuple represents an (x, y) position
# Cache of shape partitions. This is a two-level dictionary where the outer key is a shape, and the inner key is a sub-shape where the value is a list of the shapes left when the sub-shape is removed.
# there may be multiple shapes in the inner-most list if the sub-shape appears multiple times
X={}
# Transpose list of coords (flip around diagonal axis)
T=lambda s:((x,y)for y,x in s)
# Translate shape so its upper-left corner is at the origin
N=lambda s:B((x-M(s)[0],y-M(T(s))[0])for x,y in s)
# Convert shape to graph in adjacency list form
G=lambda s:{(x,y):s&{(x-1,y),(x+1,y),(x,y-1),(x,y+1)}for(x,y)in s}
# Check if graph is connected given a set of nodes, s, known to be connected
C=lambda g,s,i=0:i<=len(g)and(len(g)==len(s)or C(g,s.union(*map(g.get,s)),i+1))
# Flip shape around vertical axis
F=lambda s:N([(-x,y)for x,y in s])
# Converts shape to the minimal reflection or rotation. rotation is equivalent to transpose then flip.
P=lambda s,i=4:M([N(s),F(s),P(F(T(s)),i-1)],key=list)if i else s
# returns all the contiguous sub-shapes of s that contain the first pos, given by next(iter(s))
S=lambda s,t=B(),i=0:t|S(s,B().union(u|{p}for u in t for p in s-u if C(G(u|{p}),{p}))if i else B([B([next(iter(s))])]),i+1)if-~i<len(s)else t
# updates the sub-shape cache, X, recursively for an input shape s 
def U(s):
 k=P(s)
 if k in X:return
 j=[t for t in S(k)if C(G(k-t),{next(iter(k-t))})];X[k]={P(t):B()for t in j}
 for t in j:X[k][P(t)]|=B([B(P(k-t))]);U(t);U(k-t)
# Gets the minimum number of partitions for two shapes
V=lambda s,t:1+M(V(v,w)for u in B(X[s])&B(X[t])for v in X[s][u]for w in X[t][u])if s^t else 1
# The function to run, will update the cache for the two input shapes then return the minimum number of partitions
A=lambda s,t:U(s)or U(t)or V(P(s),P(t))