Es gibt ein Problem, bei dem ich ein Array mit Nullen füllen muss, mit den folgenden Annahmen:
0 und 1 geben
0 zu 1 und 1 zu 0 ändern
1 im Array treffen, müssen wir es in 0 ändern, so dass auch seine Nachbarn geändert werden, zum Beispiel für das Array wie das folgende: %Vor%
Wenn wir Element bei (1,1) ändern, erhalten wir das Array wie folgt:
%Vor%
1 in 0 ändern müssen, um das Array 1) Erstes Beispiel, Array ist wie folgt:
%Vor%
Die Antwort ist 1.
2) Zweites Beispiel, Array ist wie folgt:
%Vor%
Die Antwort ist 10.
Es kann auch Situationen geben, in denen es unmöglich ist, das Array auf Null zu setzen, dann sollte die Antwort "unmöglich" sein.
Irgendwie kann ich das nicht funktionieren: Für das erste Beispiel habe ich die richtige Antwort (1), aber für das zweite Beispiel sagt das Programm impossible statt 10.
Irgendwelche Ideen, was in meinem Code falsch ist?
%Vor%Ich glaube, der Grund, warum Ihr Programm in der 6x8-Matrix unmöglich zurückgegeben hat, ist, dass Sie von links nach rechts / von oben nach unten gegangen sind und jede Instanz von 1 mit 0 ersetzt haben Obwohl dies als die richtige Lösung schien, hat sie nur die 1s und 0s um die Matrix gestreut, indem sie ihre Nachbarwerte modifiziert hat. Ich denke, dass die Art, dieses Problem anzugehen, darin besteht, von unten nach oben / rechts nach links zu beginnen und die 1s in die erste Reihe zu schieben. In einer Art und Weise, die sie in eine Kurve bringt (trappt), bis sie eliminiert werden können.
Wie auch immer, hier ist meine Lösung für dieses Problem. Ich bin mir nicht ganz sicher, ob das das ist, wonach du gesucht hast, aber ich denke, es macht den Job für die drei Matrizen, die du zur Verfügung gestellt hast. Der Code ist nicht sehr ausgeklügelt und es wäre schön, ihn mit etwas schwierigeren Problemen zu testen, um zu sehen, ob er wirklich funktioniert.
%Vor%Ausgabe für matrix1 :
%Vor%Ausgabe für matrix2 :
%Vor%Ausgabe für matrix3 :
%Vor%Ausgabe für matrix4 (die Ihre ursprüngliche Frage anspricht):
%Vor%Ok, hier kommt mein etwas anderer Versuch.
Idee
Hinweis: Ich nehme an, dass "Wir können die erste Zeile nicht ändern" bedeutet "Wir können die äußerste Zeile nicht ändern.
Einige Begriffe:
Das Umschalten eines Bits ist kommutativ . Das heißt, es spielt keine Rolle, in welcher Reihenfolge wir es umschalten - das Endergebnis wird immer dasselbe sein (das ist eine triviale Aussage). Dies bedeutet, dass das Spiegeln auch eine kommutative Aktion ist, und wir sind frei, Bits in beliebiger Reihenfolge umzukehren.
Die einzige Möglichkeit, einen Wert an der Kante der Matrix umzuschalten, besteht darin, das Bit rechts daneben zu spiegeln eine ungleiche Anzahl von Malen . Da wir nach den niedrigst möglichen Flips suchen, wollen wir es maximal 1 mal drehen. In einem Szenario wie dem unten stehenden muss x genau einmal gespiegelt werden, und y muss genau 0 mal gespiegelt werden.
Daraus können wir zwei Schlussfolgerungen ziehen:
Eine Ecke der Matrix kann niemals umgeschaltet werden - wenn eine 1 an der Ecke gefunden wird, ist es mit keiner Anzahl von Flips möglich, die Matrix auf Null zu setzen. Ihr erstes Beispiel kann somit verworfen werden, ohne dass Sie sogar ein einzelnes Bit umdrehen.
Ein Bit neben einer Ecke muss denselben Wert wie das Bit auf der anderen Seite haben. Diese Matrix , die Sie in einem Kommentar gepostet haben, kann also auch verworfen werden, ohne ein einzelnes Bit umzudrehen (rechte untere Ecke) .
Zwei Beispiele für die obigen Bedingungen:
%Vor% Nicht möglich, da x genau einmal genau einmal und genau gewendet werden muss.
Möglich, x muss genau einmal gespiegelt werden.
Algorithmus
Wir können jetzt ein rekursives Argument machen und schlage folgendes vor:
m by n Matrix. impossible . m - 2 by n - 2 -Matrix (oberste und letzte Zeile entfernt, linke und rechte Spalte), wenn eine der beiden Dimensionen & gt; 2, ansonsten den Zähler ausdrucken und beenden. Implementierung
Ich hatte anfangs gedacht, dass dies schön und schön werden würde, aber ehrlich gesagt ist es ein bisschen mühsamer, als ich ursprünglich gedacht hätte, da wir viele Indizes im Auge behalten müssen. Bitte stellen Sie Fragen, wenn Sie sich über die Implementierung wundern, aber es ist im Wesentlichen eine reine Übersetzung der oben genannten Schritte.
%Vor%Ausgabe
%Vor%%Vor%unmöglich
%Vor%1
%Vor%10
unmöglich
Wenn Tab [0] [j] 1 ist, müssen Sie Tab [1] [j] um es zu löschen. Sie können dann Zeile 1 nicht umschalten, ohne Zeile 0 zu löschen. Es scheint also ein Reduktionsschritt zu sein. Sie wiederholen den Schritt, bis eine Zeile übrig ist. Wenn diese letzte Reihe nicht durch Glück klar ist, ist meine Intuition, dass es der "unmögliche" Fall ist.
%Vor%Das Problem wird folgendermaßen ausgedrückt:
%Vor%Aber es ist einfach, wenn Sie so darüber nachdenken:
%Vor%Es ist die gleiche Sache, aber jetzt ist die Lösung offensichtlich - Sie müssen alle 1en in Reihe 0 drehen, was einige Bits in den Reihen 1 und 2 dreht, dann müssen Sie alle 1en in Reihe 1 drehen, usw., bis du zu Ende kommst.
Wenn dies tatsächlich das Lights Out-Spiel ist, dann gibt es viele Ressourcen, die detailliert beschreiben, wie das Spiel zu lösen ist. Es ist auch ziemlich wahrscheinlich, dass dies ein Duplikat von Lights out Spiel-Algorithmus ist, wie es bereits geschehen ist von anderen Plakaten erwähnt.
Schauen wir mal, ob wir das erste Beispielrätsel nicht lösen können und zumindest eine konkrete Beschreibung eines Algorithmus präsentieren.
Das anfängliche Puzzle scheint lösbar zu sein:
%Vor%Der Trick besteht darin, dass Sie 1 in der obersten Zeile löschen können, indem Sie die Werte in der darunter liegenden Zeile ändern. Ich gebe die Koordinaten nach Zeile und Spalte mit einem 1-basierten Offset an, was bedeutet, dass der obere linke Wert (1, 1) und der untere rechte Wert (3, 3) ist.
Ändern (2, 1), dann (2, 3), dann (3, 2). Ich zeige die Zwischenzustände der Karte mit dem * für die Zelle, die im nächsten Schritt geändert wird.
%Vor%Diese Karte kann gelöst werden, und die Anzahl der Züge scheint 3 zu sein.
Der Pseudoalgorithmus ist wie folgt:
%Vor%Ich hoffe, das hilft; Ich kann bei Bedarf weiter ausführen, aber das ist der Kern der Standard-Lights-Out-Lösung. BTW, es ist mit Gaussian Elimination verwandt; Lineare Algebra taucht in einigen seltsamen Situationen auf:)
Was schließlich mit Ihrem Code nicht stimmt, scheint die folgende Schleife zu sein:
%Vor%Einige Probleme tauchen auf, aber erste Annahmen wieder:
Wenn dies der Fall ist, dann wird folgendes beobachtet:
Fügen Sie diese zusammen und Sie haben:
%Vor%