[Python] AGC043A (problème de lecture et de DP) [At Coder]

Lisons et comprenons le problème! N'abandonnez pas immédiatement même si vous rencontrez un problème difficile!

AGC043A Difficulty:803 Fort ennemi! Mais si vous effacez les deux points suivants, ce problème peut être résolu! ① Capacité de lecture de problèmes ② DP (méthode de planification dynamique)

① Capacité de lecture de problèmes

Les "opérations suivantes" dans la seconde moitié de l'énoncé du problème ne m'est pas du tout venu à l'esprit! Ici, nous déchiffrerons "les opérations suivantes". La partie de "l'opération suivante" est citée du problème

Choisissez quatre nombres entiers r0, c0, r1, c1 (1 ≤ r0 ≤ r1 ≤ H, 1 ≤ c0 ≤ c1 ≤ W). Changer la couleur de (r, c) pour tout r, c satisfaisant r0 ≤ r ≤ r1, c0 ≤ c ≤ c1. Autrement dit, si elle est blanche, elle est noire et si elle est noire, elle est blanche.

？？？

N'abandonnez jamais! Prenons un exemple concret pour le moment! Préparez un cahier et un stylo!

• Les notes et stylos sont indispensables pour les professionnels de la compétition! De [Python] ABC159D (High School Mathematics nCr) [At Coder]

Par exemple, disons que vous avez un chiffre 4 * 4 comme celui-ci.

Pour le moment, peignez en noir et blanc.

Le coin supérieur gauche (0,0) est le début et le coin inférieur droit (3,3) est le but. Vous ne pouvez aller à droite ou en bas que sur le chemin! Le blanc est la route. Le noir se sent comme un obstacle. Je me demande s'il faut aller à droite ou à gauche à partir de maintenant (0,0)! Voici "l'opération ci-dessous"!

Choisissez quatre nombres entiers r0, c0, r1, c1 (1 ≤ r0 ≤ r1 ≤ H, 1 ≤ c0 ≤ c1 ≤ W).

Il semble que r0, c0, r1, c1 (r est une ligne, c est une colonne) peuvent être sélectionnés comme vous le souhaitez (arbitrairement) dans les conditions ci-dessus. r0,c0,r1,c1 = 1,0,3,2 *** r et c valent 1 ou plus (commencent en haut à gauche (1,1) dans l'énoncé du problème), mais soyez prudent car mon image commence en haut à gauche (0,0) en raison de l'index. ** ** Si tu essayes ...

Changer la couleur de (r, c) pour tout r, c satisfaisant r0 ≤ r ≤ r1, c0 ≤ c ≤ c1. Autrement dit, si elle est blanche, elle est noire et si elle est noire, elle est blanche.

Avec cela, "l'opération" se fait une fois!

Ensuite, il y a un itinéraire qui vous permet d'aller en bas à droite sans aucune opération! Par conséquent, la réponse correcte à cette question est "1" fois.

** Ce que vous pouvez voir à partir d'ici, c'est que si le noir (comme un obstacle) est connecté, il peut être changé en blanc (route) avec une seule "opération"! ** **

à propos de ça!

Une fois que vous avez compris cela, il ne vous reste plus qu'à implémenter le programme!

En prime, c'est un chat, Afin de pouvoir comprendre (décrypter) le problème rapidement et avec précision dans le concours réel Il est nécessaire d'améliorer la capacité de lire les problèmes. Je pense personnellement qu'il existe deux façons d'améliorer la capacité de lecture de problèmes.

--A: résoudre de nombreux problèmes difficiles en japonais (devenir capable de résoudre des modèles similaires) ――B: Lorsque vous rencontrez un problème difficile en japonais, prenez l'habitude de penser avec un cahier et un stylo sans regarder l'explication (sans fuir) (vous ne pouvez l'apprendre que dans des batailles réelles)

② DP (méthode de planification dynamique)

① était long, Si vous comprenez le contenu de ① et comprenez ensuite les bases de DP, vous devriez être en mesure de résoudre ce problème!

• La norme en moi de «Bases de DP» est de savoir si les deux problèmes suivants de Kaeru-kun peuvent être résolus.

• Frog1
• Frog2

Conceptuellement

―― Pensez à la première ligne et à la première colonne séparément (dans mon image, la valeur initiale de dpmap est définie) ――À partir de la 2ème ligne et de la 2ème colonne, cela donne l'impression de placer le motif qui vient d'en haut et le motif qui vient de la gauche avec le plus petit nombre d'opérations dans le dpmap du tableau bidimensionnel.

• La réponse finale est en bas à droite de dpmap (dpmap [-1] [-1])

①+②

En résumé, ça ressemble à ça.

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: #Ligne 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: #Autre que la ligne 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])

Ce problème n'est pas si difficile pour l'algorithme lui-même (c'est juste un tableau à deux dimensions, qui est le niveau de base de DP). L'énoncé du problème est difficile et la difficulté augmente. Pour le dire autrement, si vous pouvez améliorer votre capacité de lecture de problèmes, le taux augmentera immédiatement! !! !! Bonne chance!

fin!