[Python] AGC043A (Problemlesefähigkeit und DP) [At Coder]

Lesen und verstehen wir das Problem! Geben Sie nicht sofort auf, auch wenn Sie auf eine schwierige Problemstellung stoßen!

AGC043A Difficulty:803 Starker Feind! Wenn Sie jedoch die folgenden zwei Punkte klären, kann dieses Problem gelöst werden! ① Problem Lesefähigkeit ② DP (Dynamische Planungsmethode)

① Problem Lesefähigkeit

Die "folgenden Operationen" in der zweiten Hälfte der Problemstellung sind mir überhaupt nicht in den Sinn gekommen! Hier werden wir "die folgenden Operationen" entschlüsseln. Der Teil der "folgenden Operation" wird aus dem Problem zitiert

Wählen Sie vier ganze Zahlen r0, c0, r1, c1 (1 ≤ r0 ≤ r1 ≤ H, 1 ≤ c0 ≤ c1 ≤ W). Ändern Sie die Farbe von (r, c) für alle r, c, die r0 ≤ r ≤ r1, c0 ≤ c ≤ c1 erfüllen. Das heißt, wenn es weiß ist, ist es schwarz, und wenn es schwarz ist, ist es weiß.

？？？

Gib nie auf! Lassen Sie uns vorerst über ein konkretes Beispiel nachdenken! Bereiten Sie ein Notizbuch und einen Stift vor!

• Notizen und Stifte sind für Wettkampfprofis unverzichtbar! Aus [Python] ABC159D (High School Mathematics nCr) [At Coder]

Angenommen, Sie haben eine solche 4 * 4-Zahl.

Malen Sie vorerst schwarz und weiß.

Oben links (0,0) ist der Start und unten rechts (3,3) ist das Ziel. Sie können nur als Route auf dem Weg nach rechts oder unten gehen! Weiß ist die Straße. Schwarz fühlt sich wie ein Hindernis an. Ich frage mich, ob ich von jetzt an nach rechts oder links gehen soll (0,0)! Hier kommt die "Operation unten"!

Wählen Sie vier ganze Zahlen r0, c0, r1, c1 (1 ≤ r0 ≤ r1 ≤ H, 1 ≤ c0 ≤ c1 ≤ W).

Es scheint, dass r0, c0, r1, c1 (r ist Zeile, c ist Spalte) unter den oben genannten Bedingungen (beliebig) nach Belieben ausgewählt werden kann. r0,c0,r1,c1 = 1,0,3,2 *** r und c sind 1 oder mehr (beginnen oben links (1,1) in der Problemstellung), aber seien Sie vorsichtig, da mein Bild aufgrund des Index oben links (0,0) beginnt. ** **. Wenn du es versuchst ...

Ändern Sie die Farbe von (r, c) für alle r, c, die r0 ≤ r ≤ r1, c0 ≤ c ≤ c1 erfüllen. Das heißt, wenn es weiß ist, ist es schwarz, und wenn es schwarz ist, ist es weiß.

Damit wird "Operation" einmal durchgeführt!

Dann gibt es eine Route, mit der Sie ohne Operation nach rechts unten gehen können! Daher ist die richtige Antwort auf diese Frage "1" mal.

** Was Sie von hier aus sehen können, ist, dass wenn Schwarz (wie ein Hindernis) angeschlossen ist, es mit einer "Operation" in Weiß (Straße) geändert werden kann! ** **.

darüber!

Sobald Sie dies verstanden haben, müssen Sie nur noch das Programm implementieren!

Als Bonus ist es ein Chat, Um das Problem im eigentlichen Wettbewerb schnell und genau verstehen (entschlüsseln) zu können Es ist notwendig, die Fähigkeit zum Lesen von Problemen zu verbessern. Ich persönlich denke, dass es zwei Möglichkeiten gibt, die Fähigkeit zum Lesen von Problemen zu verbessern.

--A: Löse viele schwierige Probleme auf Japanisch (werde in der Lage, ähnliche Muster zu lösen) ――B: Wenn Sie auf Japanisch auf ein schwieriges Problem stoßen, gewöhnen Sie sich an, mit einem Notizbuch und einem Stift zu denken, ohne auf die Erklärung zu achten (ohne wegzulaufen) (Sie können es nur in tatsächlichen Schlachten lernen).

② DP (Dynamische Planungsmethode)

① war lang, Wenn Sie den Inhalt von ① verstehen und dann die Grundlagen von DP verstehen, sollten Sie in der Lage sein, dieses Problem zu lösen!

• Der Standard in mir von "Basics of DP" ist, ob die folgenden zwei Kaeru-Kun-Probleme gelöst werden können.

• Frog1
• Frog2

Konzeptionell

――Denken Sie die erste Zeile und die erste Spalte getrennt (in meinem Bild ist der Anfangswert von dpmap festgelegt). ―― Ab der 2. Zeile und 2. Spalte fühlt es sich an, als würde das Muster von oben und das Muster von links mit der geringeren Anzahl von Operationen in die dpmap des zweidimensionalen Arrays eingefügt.

• Die endgültige Antwort ist rechts unten in dpmap (dpmap [-1] [-1]).

①+②

Zusammenfassend sieht es so aus.

test.py

def LI(): return list(map(int,input().split()))
H,W = LI()
S = [input() for _ in range(H)]
dp = [[-1]*W for _ in range(H)]
for i in range(H):
    for j in range(W):
        judge = 1 if S[i][j]=='#' else 0
        if i==0: #Zeile 0
            if j==0:
                dp[0][0] = judge
            else:
                dp[0][j] = dp[0][j-1]+judge*(0 if S[0][j-1]=='#' else 1)
        else: #Andere als Zeile 0
            if j==0:
                dp[i][0] = dp[i-1][0]+judge*(0 if S[i-1][0]=='#' else 1)
            else:
                temp1 = dp[i][j-1]+judge*(0 if S[i][j-1]=='#' else 1)
                temp2 = dp[i-1][j]+judge*(0 if S[i-1][j]=='#' else 1)
                dp[i][j] = min(temp1,temp2)
print(dp[-1][-1])

Dieses Problem ist für den Algorithmus selbst nicht so schwierig (es ist nur ein zweidimensionales Array, das die Grundstufe von DP darstellt). Die Problemstellung ist schwierig und die Schwierigkeit steigt. Um es anders herum auszudrücken: Wenn Sie Ihre Fähigkeit zum Lesen von Problemen verbessern können, steigt die Rate sofort! !! !! Viel Glück!

Ende!