Je garderai une trace des problèmes que j'ai commis une erreur dans les questions passées d'AtCoder et des problèmes qui m'ont marqué.
3RE
J'ai fait beaucoup d'erreurs stupides, alors je me dépêchais de le résoudre.
La politique de base est que lors du changement du nombre de $ A_ {i, j} $ à 1, il faut du temps pour trouver la puissance magique minimale pour changer ce nombre à 1, alors appliquez d'abord chaque puissance magique minimale à la méthode WF. C'est une politique de le demander en utilisant.
J'ai ressenti une croissance au point où j'ai trouvé le pouvoir magique minimum (en changeant les nombres) → Méthode WF, mais quand je l'ai réécrit, j'ai fait une erreur dans la valeur d'index et c'est devenu RE. C'était. ** (J'ai changé l'endroit en j en i.)
De plus, si vous écrivez comme [] * n **, vous ne remarquerez pas que chaque tableau pointe vers le même objet **, vous ferez une erreur au moment de la saisie, et il faudra du temps pour y déboguer. J'ai.
answerD.py
dp=[[0 for j in range(10)] for i in range(10)]
h,w=map(int,input().split())
for i in range(10):
s=list(map(int,input().split()))
for j in range(10):
dp[i][j]=s[j]
#L'image de la méthode WF est de considérer le temps le plus court sans passer par d'autres, d'augmenter les places qui peuvent être passées à partir de là, et de prendre des min de plus en plus.
for k in range(10):
for i in range(10):
for j in range(10):
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])
c=0
for i in range(h):
s=list(map(int,input().split()))
for j in range(w):
#J'ai fait une erreur dans l'indice ici
if s[j]!=-1 and s[j]!=1:
c+=dp[s[j]][1]
print(c)
J'étais accro comme jamais auparavant, alors j'ai beaucoup appris en même temps que je me fanais.
Ce problème peut être résolu en ** réfléchissant au modèle qui peut être atteint dans le temps le plus court entre le point de départ (1,1) et le point final (H, W) **. (C'est un peu difficile de trouver cette idée ??)
Plus précisément, nous l'avons implémenté en accédant aux quatre carrés adjacents qui peuvent être atteints à partir du carré à ce moment-là et en mettant à jour les informations des carrés arrivés. Aussi, comme ce que nous voulons trouver est un modèle qui peut être atteint dans les plus brefs délais, s'il n'est pas le plus court depuis le point de départ, nous avons imaginé un moyen de réduire la quantité de calcul en arrêtant la récurrence là-bas sans mettre à jour les informations des carrés.
Cela n'a pas été difficile tant que j'ai trouvé une méthode, mais il semble que ma méthode n'était pas la meilleure, et en Python ** la récursivité était trop profonde et elle est devenue RE **. (C'était ma première expérience. Dans le cas de RE, je pensais que c'était une référence hors service.)
Quand j'ai vérifié ici, il semblait que ** en Python, la profondeur de récurrence est fixée dans chaque environnement **, donc la fonction setrecursionlimit '' du module sys (la fonction qui définit la profondeur de récurrence) A été utilisé. J'ai défini moi-même la profondeur de récurrence avec la fonction setrecursionlimit '' et forcé de quitter quand il était sur le point de dépasser cette profondeur.
De plus, je ne voulais pas le résoudre avec cette solution, donc lorsque je l'ai réécrit en C ++, j'ai pu AC sans définir la profondeur de récurrence. (De plus, j'ai appris ici que vous pouvez ** a <= x <= b en Python mais pas en C ++ **.)
answerD.py
import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())
def go_next(I,J,n):
n+=1
global dp,w,h
if n>1000:
return
if I<h-1:
if x[I+1][J]=="." and dp[I+s1][J]>dp[I][J]+1:
dp[I+1][J]=dp[I][J]+1
go_next(I+1,J,n)
if 0<I:
if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
dp[I-1][J]=dp[I][J]+1
go_next(I-1,J,n)
if J<w-1:
if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
dp[I][J+1]=dp[I][J]+1
go_next(I,J+1,n)
if 0<J:
if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
dp[I][J-1]=dp[I][J]+1
go_next(I,J-1,n)
x=[]
for i in range(h):
x.append(list(input()))
#print(x)
c=0
for i in range(h):
for j in range(w):
if x[i][j]==".":
c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
#Prise en compte lorsque vous ne pouvez pas atteindre
if dp[h-1][w-1]==10000000000:
print(-1)
else:
print(c-dp[h-1][w-1])
answerD.cc
#include<iostream>
#include<vector>
#include<string>
using namespace std;
typedef vector< vector<int> > vv;
#define INF 1e9
void go_next(int I,int J,vv& dp,vector<string> x,int w,int h){
if(I<h-1){
if(x[I+1][J]=='.' and dp[I+1][J]>dp[I][J]+1){
dp[I+1][J]=dp[I][J]+1;go_next(I+1,J,dp,x,w,h);
}
}
if(0<I){
if(x[I-1][J]=='.' and dp[I-1][J]>dp[I][J]+1){
dp[I-1][J]=dp[I][J]+1;go_next(I-1,J,dp,x,w,h);
}
}
if(J<w-1){
if(x[I][J+1]=='.' and dp[I][J+1]>dp[I][J]+1){
dp[I][J+1]=dp[I][J]+1;go_next(I,J+1,dp,x,w,h);
}
}
if(0<J){
if(x[I][J-1]=='.' and dp[I][J-1]>dp[I][J]+1){
dp[I][J-1]=dp[I][J]+1;go_next(I,J-1,dp,x,w,h);
}
}
}
int main(){
int h ,w;cin >> h >> w;
vv dp(h,vector<int>(w,INF));dp[0][0]=1;
vector<string> x(h);for(int i=0;i<h;i++)cin >>x[i];
int c=0;
for(int i=0;i<h;i++){
for(int j=0;j<w;j++){
if(x[i][j]=='.'){c+=1;}
}
}
go_next(0,0,dp,x,w,h);
if(dp[h-1][w-1]==INF)cout << -1 << endl;
else cout << c-dp[h-1][w-1] << endl;
}
Recommended Posts