Ich werde die Probleme aufzeichnen, die ich in den letzten Fragen von AtCoder falsch gemacht habe, und die Probleme, die mich beeindruckt haben.
3RE
Ich habe viele dumme Fehler gemacht, also habe ich mich beeilt, sie zu lösen.
Die grundlegende Richtlinie lautet, dass es beim Ändern der Anzahl von $ A_ {i, j} $ auf 1 einige Zeit dauert, die minimale magische Kraft zu finden, um diese Zahl auf 1 zu ändern. Wenden Sie also zuerst jede minimale magische Kraft auf die WF-Methode an. Es ist eine Richtlinie, mit zu fragen.
Ich spürte ein Wachstum bis zu dem Punkt, an dem ich die minimale magische Kraft (beim Ändern der Zahlen) → WF-Methode fand, aber als ich es umschrieb, machte ich einen Fehler im Indexwert und es wurde RE. Es war. ** (Ich habe den Ort in j in i geändert.)
Wenn Sie wie [] * n ** schreiben, werden Sie nicht bemerken, dass jedes Array auf dasselbe Objekt zeigt **. Sie werden zum Zeitpunkt der Eingabe einen Fehler machen und es wird einige Zeit dauern, bis Sie dort debuggen. Ich habe.
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]
#Das Bild der WF-Methode besteht darin, die kürzeste Zeit zu berücksichtigen, ohne andere zu durchlaufen, die Stellen zu vergrößern, die von dort aus passiert werden können, und immer mehr Minuten zu benötigen.
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):
#Ich habe hier im Index einen Fehler gemacht
if s[j]!=-1 and s[j]!=1:
c+=dp[s[j]][1]
print(c)
Ich war süchtig danach wie nie zuvor und lernte viel, während ich verdorrte. Dieses Problem kann gelöst werden, indem ** über das Muster nachgedacht wird, das in kürzester Zeit vom Startpunkt (1,1) bis zum Endpunkt (H, W) ** erreicht werden kann. (Es ist ein wenig schwierig, auf diese Idee zu kommen?) Insbesondere haben wir es implementiert, indem wir zu den vier benachbarten Quadraten gegangen sind, die zu diesem Zeitpunkt vom Quadrat aus erreichbar sind, und die Informationen der angekommenen Quadrate aktualisiert haben. Da wir ein Muster finden möchten, das in kürzester Zeit erreicht werden kann, haben wir einen Weg gefunden, um den Rechenaufwand zu reduzieren, indem wir die Wiederholung dort stoppen, ohne die Informationen der Quadrate zu aktualisieren. Es war nicht schwierig, solange ich eine Methode entwickelte, aber es scheint, dass meine Methode nicht die beste war, und in Python ** war die Rekursion zu tief und wurde zu RE **. (Es war meine erste Erfahrung. Im Fall von RE dachte ich, es sei eine Referenz außerhalb der Reihenfolge.) Als ich hier nachgesehen habe, schien es, dass ** in Python die Wiederholungstiefe in jeder Umgebung festgelegt ist **, also die Funktion `` `setrecursionlimit``` des sys-Moduls (die Funktion, die die Wiederholungstiefe festlegt). Wurde benutzt. Ich habe die Wiederholungstiefe selbst mit der Funktion "setrecursionlimit" definiert und musste sie verlassen, wenn sie diese Tiefe überschreiten wollte. Außerdem wollte ich es nicht mit dieser Lösung lösen. Als ich es in C ++ umschrieb, konnte ich AC-Einstellungen vornehmen, ohne die Wiederholungstiefe festzulegen. (Außerdem habe ich hier gelernt, dass ** Python a <= x <= b kann, C ++ jedoch nicht **.)
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)
#Überlegung, wann Sie nicht erreichen können
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