[PYTHON] AtCoder Beginner Contest 170 Bewertung
Die Ergebnisse dieser Zeit
Eindrücke dieser Zeit
Ich habe nach langer Zeit einen großen Fehler gemacht. Ich dachte nicht, dass D nicht bestehen würde, aber wenn Sie ruhig denken, können Sie es mit Python oder PyPy in Bezug auf das Rechenvolumen nicht bestehen ... Ich habe E in der zweiten Hälfte gelöst, aber es tut weh, einen Fehler in der Implementierung zu haben ... Die Geschwindigkeit der Implementierung scheint wiederholt trainiert werden zu müssen, um sich daran zu gewöhnen.
Als ich Code Golf spielte, kam ich zu spät, um einen Artikel zu veröffentlichen. Ich werde versuchen, Code Golf zu spielen, nachdem ich die Bewertung abgeschlossen habe ...
Problem A
Da es sich nach dem Ersetzen von 0 um eine Ganzzahlzeichenfolge handelt, kann der Index des Elements, das zu 0 wird, durch 1-Index berechnet werden.
A.py
x=list(map(int,input().split()))
print(x.index(0)+1)
B-Problem
Überlegen Sie, wie viele Tiere Kraniche bzw. Schildkröten sind. Es gibt 0 bis x Kraniche und Schildkröten, und wenn Sie entscheiden, wie viele von ihnen sind, wird der andere entschieden, und wenn Sie wissen, wie viele von ihnen, wird die Anzahl der Beine bestimmt. Suchen Sie also nach einer Kombination, die y ist.
B.py
x,y=map(int,input().split())
for i in range(x+1):
if 2*i+4*(x-i)==y:
print("Yes")
break
else:
print("No")
C-Problem
Vor kurzem habe ich das Gefühl, dass es in C einige Probleme gibt, über die man nachdenken muss.
Ganzzahl berechnen
C.py
x,n=map(int,input().split())
p=sorted(list(map(int,input().split())))
q=[0]*(102)
for i in range(n):
q[p[i]]=1
ans=(1000000,-1)
for i in range(102):
if q[i]==0:
if ans[0]>abs(i-x):
ans=(abs(i-x),i)
print(ans[1])
D Problem
In der Antwort wurde geschrieben, dass dies mit derselben Operation wie beim Eratostenes-Sieb durchgeführt werden kann, aber ich musste $ O (N \ sqrt { A_ {max}}) Ich habe es mit $ bestanden. Da der Rechenaufwand für Python und PyPy kaum ausreicht, habe ich ihn in C ++ geändert. Außerdem konnte ich diese Entscheidung während des Wettbewerbs nicht treffen, daher hatte ich das Gefühl, dass ich ** ruhig sein sollte. ** Wenn $ A_i $ durch $ A_j $ teilbar ist, ist $ A_j $ ein Bruchteil von $ A_i $ **. Wie Sie aus diesem Artikel ersehen können, können Sie die Brüche auch mit $ O (\ log {A_i}) $ aufzählen. Daher ist es möglich, die Brüche für jedes $ A_i $ aufzulisten und festzustellen, dass die Eigenschaften der Problemstellung nicht erfüllt sind, wenn die Brüche in der Sequenz $ A $ enthalten sind.
Als zusätzliche Anmerkung, als ich Herrn maspys Kommentar betrachtete, dachte ich, es sei wahr, dass geschrieben wurde, dass es einfacher sei, ein Vielfaches als einen Bruchteil in der Reihenfolge der Beziehungen zu finden. Ich möchte es von nun an verwenden.
D.cc
//Einschließen(Alphabetischer Reihenfolge)
#include<algorithm>//sort,Halbierungssuche,Eine solche
#include<bitset>//Bit mit fester Länge gesetzt
#include<cmath>//pow,Protokoll usw.
#include<complex>//Komplexe Zahl
#include<deque>//Double-Ended-Zugriffswarteschlange
#include<functional>//größer sortieren
#include<iomanip>//setprecision(Gleitkomma-Ausgabefehler)
#include<iostream>//Input-Output
#include<iterator>//Betrieb einstellen(Produktset,Summensatz,Differenzsatz etc.)
#include<map>//map(Wörterbuch)
#include<numeric>//iota(Generierung einer Ganzzahlzeichenfolge),gcd und lcm(c++17)
#include<queue>//Warteschlange
#include<set>//einstellen
#include<stack>//Stapel
#include<string>//String
#include<unordered_map>//Karte mit Iterator, aber ohne Ordnung
#include<unordered_set>//Es gibt einen Iterator, aber die Reihenfolge wird nicht festgelegt
#include<utility>//pair
#include<vector>//Array mit variabler Länge
using namespace std;
typedef long long ll;
//Makro
//für Schleifenbeziehung
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Endungen)、のどちらOder
//Wenn es kein D gibt, wird die Schleifenvariable um 1 erhöht, und wenn es ein D gibt, wird die Schleifenvariable um 1 dekrementiert.
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//x ist ein Container wie ein Vektor
#define ALL(x) (x).begin(),(x).end() //Ich möchte Argumente wie sort weglassen
#define SIZE(x) ((ll)(x).size()) //Größe zu Größe_Wechseln Sie von t nach ll
#define MAX(x) *max_element(ALL(x)) //Finden Sie den Maximalwert
#define MIN(x) *min_element(ALL(x)) //Finden Sie den Mindestwert
//Konstante
#define INF 1000000000000 //10^12:Extrem großer Wert,∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays(Wird für die Aufzählung von Primzahlen usw. verwendet.)
//Abkürzung
#define PB push_back //In Vektor einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares
vector<ll> make_divisors(ll n){
vector<ll> divisors;
//cout << 1 << endl;
FOR(i,1,ll(sqrt(n))){
if(n%i==0){
divisors.PB(i);
if(i!=ll(n/i))divisors.PB(ll(n/i));
}
}
return divisors;
}
signed main(){
ll n;cin >> n;
map<ll,ll> a;
REP(i,n){
ll x;cin >> x;
a[x]+=1;
}
ll ans=0;
for(auto i=a.begin();i!=a.end();i++){
vector<ll> div=make_divisors(i->F);
//cout << 1 << endl;
ll f=true;
REP(j,SIZE(div)){
if((a.find(div[j])!=a.end() and div[j]!=(i->F))or(div[j]==(i->F) and (i->S)>1)){
f=false;
break;
}
}
if(f)ans++;
}
cout << ans << endl;
}
E Problem
Das Multiset, das ich letzte Woche gemacht habe, ist herausgekommen, aber ich konnte es aufgrund eines Fehlers in der Implementierung nicht lösen ...
Zuerst ** müssen Sie das Kleinkind mit der höchsten Rate in jedem Garten aufbewahren **, bereiten Sie also einen Behälter vor, um dies (youjitati) aufzubewahren. Außerdem muss ** das Kind mit der höchsten Rate in jedem Garten auch in einem Behälter ** (youtien) aufbewahrt werden, aber ** Yojitati und Yotien-Elemente können sich je nach Änderung des Gartens ändern **, sodass nur das Kind mit der höchsten Rate Sie müssen stattdessen sowohl youjitati als auch youtien als sortierten Behälter ** aufbewahren.
Hier sind ** C ++ set, multiset ** Beispiele für ($ O (\ log {n}) $) Container **, die unter Beibehaltung des sortierten Status (Python) mit hoher Geschwindigkeit hinzugefügt oder gelöscht werden können. Es gibt auch eine Heap-Warteschlange, die jedoch nicht intuitiv zu bedienen ist und nur schwer persönlich zu verwenden ist.) Auch hier habe ich beschlossen, ein Multiset zu verwenden, das die Rate und Nummer des Kindes als Paar speichert, um Säuglinge mit derselben Rate zu unterscheiden. Da dies jedoch durch Pairing unterschieden werden kann, ist das Ergebnis für Sets anstelle von Multiset dasselbe Sie können ein Programm wie dieses schreiben.
Wenn Sie das oben Genannte organisieren, speichert youjitati daher die Säuglinge mit der höchsten Rate in jedem Kindergarten in aufsteigender Reihenfolge mit dem Paar <Säuglingsrate, Säuglingsnummer> mit multiset <Paar <ll, ll >> und youtien Speichert die Raten jedes Kindergarten-Kleinkindes in aufsteigender Reihenfolge mit vector <multiset <pair <ll, ll >>>.
Erwägen Sie, jede Abfrage unter dieser zu verarbeiten. Hier werden wir erwägen, das Kind C vom Kindergarten E in den Kindergarten D zu überführen, aber ** der Kindergarten E, zu dem das Kind C gehört, kann aus den zuvor erwähnten Behältern youjitati und youtien nicht verstanden werden **. Notieren Sie daher einfach in vector <ll> (doko) **, in welchem Kindergarten sich jedes Kleinkind befindet **. Lassen Sie uns auf dieser Grundlage über die Abfrageverarbeitung mit Diagrammen nachdenken.
Betrachten Sie zunächst den Fall, in dem youtuien genug Kleinkinder hat. Hier ist es leicht zu verstehen, ob es in ** Stufen ** unterteilt ist, und es kann in drei Stufen unterteilt werden. (** Ich konnte die Produktion bisher nicht organisieren . Ich denke, ich muss Vertrauen gewinnen, weil ich es lösen kann, wenn ich mich beruhige.)
① aus youjitati löschen
Zunächst muss die in youjitati gespeicherte maximale Anzahl von Säuglingen des Kindergartens D und des Kindergartens E einmal gelöscht werden, da sich die in youjitati zu speichernden Elemente ändern können, wenn sich das Kind C bewegt. Hier kann die maximale Rate Säuglinge im Kindergarten D und Kindergarten E im Iterator als "--youtien [D] .end ()", "--youtien [E] .end ()" erhalten werden. ( Es ist erfrischend zu denken, dass du einmal fliehen solltest **.)
② Bewegung des Säuglings C.
Bewegen Sie am Ende von ① das Kind C vom Kindergarten E in den Kindergarten D. Zu diesem Zeitpunkt müssen Sie bei der Suche nach dem Element von Säugling C nach <Säuglingsrate, Säuglingsnummer> suchen, und ** die Säuglingsrate kann nicht so erhalten werden, wie sie ist **, sodass jede Säuglingsrate ein Vektor ist. Nimm es in
Dies ist auch , wenn in youtien genügend Kleinkinder vorhanden sind ** und möglicherweise nicht genügend Kleinkinder zum Löschen vorhanden sind. In diesem Fall ist es gut, den Fall wie im folgenden Code gezeigt zu teilen, aber wenn die Größe von ** youtien [E] und youtien [D] 0 ist, können Sie einfach nicht arbeiten ** Ich habe später festgestellt, dass ( Vereinfachung solcher Probleme ist sehr wichtig **).
Wiederholen Sie den obigen Vorgang für jede Abfrage, holen Sie das kleinste Element mit youjitati mit youjitati.begin () und geben Sie es aus.
E.cc
//Einschließen(Alphabetischer Reihenfolge)
#include<algorithm>//sort,Halbierungssuche,Eine solche
#include<bitset>//Bit mit fester Länge gesetzt
#include<cmath>//pow,Protokoll usw.
#include<complex>//Komplexe Zahl
#include<deque>//Double-Ended-Zugriffswarteschlange
#include<functional>//größer sortieren
#include<iomanip>//setprecision(Gleitkomma-Ausgabefehler)
#include<iostream>//Input-Output
#include<iterator>//Betrieb einstellen(Produktset,Summensatz,Differenzsatz etc.)
#include<map>//map(Wörterbuch)
#include<numeric>//iota(Generierung einer Ganzzahlzeichenfolge),gcd und lcm(c++17)
#include<queue>//Warteschlange
#include<set>//einstellen
#include<stack>//Stapel
#include<string>//String
#include<unordered_map>//Karte mit Iterator, aber ohne Ordnung
#include<unordered_set>//Es gibt einen Iterator, aber die Reihenfolge wird nicht festgelegt
#include<utility>//pair
#include<vector>//Array mit variabler Länge
using namespace std;
typedef long long ll;
//Makro
//für Schleifenbeziehung
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Endungen)、のどちらOder
//Wenn es kein D gibt, wird die Schleifenvariable um 1 erhöht, und wenn es ein D gibt, wird die Schleifenvariable um 1 dekrementiert.
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//x ist ein Container wie ein Vektor
#define ALL(x) (x).begin(),(x).end() //Ich möchte Argumente wie sort weglassen
#define SIZE(x) ((ll)(x).size()) //Größe zu Größe_Wechseln Sie von t nach ll
#define MAX(x) *max_element(ALL(x)) //Finden Sie den Maximalwert
#define MIN(x) *min_element(ALL(x)) //Finden Sie den Mindestwert
//Konstante
#define INF 1000000000000 //10^12:Extrem großer Wert,∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays(Wird für die Aufzählung von Primzahlen usw. verwendet.)
//Abkürzung
#define PB push_back //In Vektor einfügen
#define MP make_pair //Paarkonstruktor
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares
signed main(){
//Code zur Beschleunigung der Eingabe
//ios::sync_with_stdio(false);
//cin.tie(nullptr);
ll f=2*pow(10,5);
ll n,q;cin >> n >> q;
vector<multiset<pair<ll,ll>>> youtien(f);
vector<ll> doko(n);
vector<ll> tikara(n);
REP(i,n){
ll a,b;cin >> a >> b;b--;
youtien[b].insert(MP(a,i));
doko[i]=b;
tikara[i]=a;
}
multiset<pair<ll,ll>> youjitati;
REP(i,f){
if(!(youtien[i].empty())){
youjitati.insert(*(--youtien[i].end()));
}
}
REP(i,q){
ll c,d;cin >> c >> d;c--;d--;
if(youtien[d].size()>0 and youtien[doko[c]].size()>1){
youjitati.erase(*(--youtien[d].end()));
youjitati.erase(*(--youtien[doko[c]].end()));
youtien[d].insert(MP(tikara[c],c));
youtien[doko[c]].erase(MP(tikara[c],c));
youjitati.insert(*(--youtien[d].end()));
youjitati.insert(*(--youtien[doko[c]].end()));
doko[c]=d;
}else if(youtien[d].size()==0 and youtien[doko[c]].size()>1){
youjitati.erase(*(--youtien[doko[c]].end()));
youtien[d].insert(MP(tikara[c],c));
youtien[doko[c]].erase(MP(tikara[c],c));
youjitati.insert(*(--youtien[d].end()));
youjitati.insert(*(--youtien[doko[c]].end()));
doko[c]=d;
}else if(youtien[d].size()>0 and youtien[doko[c]].size()==1){
youjitati.erase(*(--youtien[doko[c]].end()));
youjitati.erase(*(--youtien[d].end()));
youtien[d].insert(MP(tikara[c],c));
youtien[doko[c]].erase(MP(tikara[c],c));
youjitati.insert(*(--youtien[d].end()));
doko[c]=d;
}else{
youjitati.erase(*(--youtien[doko[c]].end()));
youtien[d].insert(MP(tikara[c],c));
youtien[doko[c]].erase(MP(tikara[c],c));
youjitati.insert(*(--youtien[d].end()));
doko[c]=d;
}
cout << (youjitati.begin())->F << endl;
}
}
F Problem
Ich kann an BFS und DFS ** denken, weil es keine ** Suche und Gewichtung auf den Quadraten der Anzahl von $ H \ mal W \ leqq 10 ^ 6 $ gibt. Da es sich um die Mindestanzahl von Zügen handelt, werde ich auch mit BFS ** suchen.
Betrachten Sie zunächst alle möglichen Kandidaten für die nächste Masse, die von jedem Rekursiven verfolgt werden sollen. Mit anderen Worten, betrachten Sie 4K-Straßen, die um K-Quadrate in vier Richtungen nach oben, unten, links und rechts vorrücken. Dies kann das nächste Quadrat sein (im Fall von @ square können Sie jedoch nicht darüber hinausgehen). Wenn Sie jedoch nach all dem suchen, werden Sie feststellen, dass Sie zu viel suchen ** (auch wenn Sie nicht wissen, dass Sie zu viel suchen, werden Sie es bemerken, wenn Sie TLE). Daher sollten Sie ** die Mindestmassenbedingung ** für eine notwendige und ausreichende Suche berücksichtigen.
Wenn ich hier tatsächlich an die vorherige Suche denke, habe ich BFS (TLE) implementiert, indem ich die bereits gesuchten Zellen übersprungen und den K-Zellen gefolgt bin. Ich hatte das Gefühl, dass es eine Verschwendung war, die bereits durchsuchten Quadrate erneut zu durchsuchen **. Mit anderen Worten, da es möglich ist, vom bereits gesuchten Quadrat zu K-Quadraten in vier Richtungen zu suchen, wurden die bereits gesuchten Quadrate bereits durchsucht. Daher habe ich berücksichtigt, dass die Suche danach endet, wenn zusätzlich zur Zelle @ eine Zelle durchsucht wurde, die bereits durchsucht wurde. Dies ist unten dargestellt.
Es ist jedoch nicht möglich, die durchsuchten Quadrate zu berücksichtigen, aber die Suche über dieses Quadrat hinaus hat noch nicht begonnen. Es kann gesagt werden, dass solche Zellen ** Zellen derselben Tiefe ** sind, und wenn es solche Zellen gibt, wird die Suche fortgesetzt. Dies ist unten dargestellt.
In Anbetracht des oben Gesagten können Sie es leicht implementieren, indem Sie es als einen etwas anderen BFS-Typ betrachten. Der Code lautet wie folgt.
F.py
import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque([[x1-1,y1-1]])
dp[x1-1][y1-1]=0
def bfs(d):
global dp,now
l=len(now)
dp_sub=deque()
cand=set()
for i in range(l):
x,y=now.popleft()
for j in range(1,min(k+1,w-y)):
if dp[x][y+j]==inf:
dp_sub+=[[x,y+j,d]]
cand.add((x,y+j))
else:
break
for j in range(1,min(k+1,y+1)):
if dp[x][y-j]==inf:
dp_sub+=[[x,y-j,d]]
cand.add((x,y-j))
else:
break
for j in range(1,min(k+1,h-x)):
if dp[x+j][y]==inf:
dp_sub+=[[x+j,y,d]]
cand.add((x+j,y))
else:
break
for j in range(1,min(k+1,x+1)):
if dp[x-j][y]==inf:
dp_sub+=[[x-j,y,d]]
cand.add((x-j,y))
else:
break
while dp_sub!=deque([]):
e=dp_sub.popleft()
dp[e[0]][e[1]]=e[2]
for i in cand:
now+=[i]
if l!=0:bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)
answerF.cc
//Einschließen(Alphabetischer Reihenfolge)
#include<algorithm>//sort,Halbierungssuche,Eine solche
#include<bitset>//Bit mit fester Länge gesetzt
#include<cmath>//pow,Protokoll usw.
#include<complex>//Komplexe Zahl
#include<deque>//Double-Ended-Zugriffswarteschlange
#include<functional>//größer sortieren
#include<iomanip>//setprecision(Gleitkomma-Ausgabefehler)
#include<iostream>//Input-Output
#include<iterator>//Betrieb einstellen(Produktset,Summensatz,Differenzsatz etc.)
#include<map>//map(Wörterbuch)
#include<numeric>//iota(Generierung einer Ganzzahlzeichenfolge),gcd und lcm(c++17)
#include<queue>//Warteschlange
#include<set>//einstellen
#include<stack>//Stapel
#include<string>//String
#include<unordered_map>//Karte mit Iterator, aber ohne Ordnung
#include<unordered_set>//Es gibt einen Iterator, aber die Reihenfolge wird nicht festgelegt
#include<utility>//pair
#include<vector>//Array mit variabler Länge
using namespace std;
typedef long long ll;
//Makro
//für Schleifenbeziehung
//Das Argument ist(Variablen in der Schleife,Bewegungsumfang)Oder(Variablen in der Schleife,Erste Nummer,Anzahl der Endungen)、のどちらOder
//Wenn es kein D gibt, wird die Schleifenvariable um 1 erhöht, und wenn es ein D gibt, wird die Schleifenvariable um 1 dekrementiert.
#define REP(i,n) for(ll i=0;i<(ll)(n);i++)
#define REPD(i,n) for(ll i=n-1;i>=0;i--)
#define FOR(i,a,b) for(ll i=a;i<=(ll)(b);i++)
#define FORD(i,a,b) for(ll i=a;i>=(ll)(b);i--)
//x ist ein Container wie ein Vektor
#define ALL(x) (x).begin(),(x).end() //Ich möchte Argumente wie sort weglassen
#define SIZE(x) ((ll)(x).size()) //Größe zu Größe_Wechseln Sie von t nach ll
#define MAX(x) *max_element(ALL(x)) //Finden Sie den Maximalwert
#define MIN(x) *min_element(ALL(x)) //Finden Sie den Mindestwert
//Konstante
#define INF 1000000000000 //10^12:Extrem großer Wert,∞
#define MOD 1000000007 //10^9+7:Gemeinsames Recht
#define MAXR 100000 //10^5:Maximale Reichweite des Arrays(Wird für die Aufzählung von Primzahlen usw. verwendet.)
//Abkürzung
#define PB push_back //In Vektor einfügen
#define MP make_pair //Paarkonstruktor
#define PF pop_front
#define F first //Das erste Element des Paares
#define S second //Das zweite Element des Paares
ll h,w,k;
vector<vector<ll>> dp;
deque<pair<ll,ll>> now;
void bfs(ll d){
ll l=SIZE(now);
if(l==0){
return;
}
deque<vector<ll>> dp_sub;
set<pair<ll,ll>> cand;
REP(i,l){
ll x,y;x=now.front().F;y=now.front().S;now.PF();
FOR(j,1,min(k,w-y-1)){
if(dp[x][y+j]==INF){
dp_sub.PB({x,y+j,d});
//dp[x][y+j]=d;
cand.insert(MP(x,y+j));
//now.PB(MP(x,y+j));
}else{
break;
}
//if(dp[x][y+j]==-1)break;
}
FOR(j,1,min(k,y)){
if(dp[x][y-j]==INF){
dp_sub.PB({x,y-j,d});
//dp[x][y-j]=d;
cand.insert(MP(x,y-j));
//now.PB(MP(x,y-j));
}else{
break;
}
//if(dp[x][y-j]==-1)break;
}
FOR(j,1,min(k,h-x-1)){
if(dp[x+j][y]==INF){
dp_sub.PB({x+j,y,d});
//dp[x+j][y]=d;
cand.insert(MP(x+j,y));
//now.PB(MP(x+j,y));
}else{
break;
}
//if(dp[x+j][y]==-1)break;
}
FOR(j,1,min(k,x)){
if(dp[x-j][y]==INF){
dp_sub.PB({x-j,y,d});
//dp[x-j][y]=d;
cand.insert(MP(x-j,y));
//now.PB(MP(x-j,y));
}else{
break;
}
//if(dp[x-j][y]==-1)break;
}
}
while(!dp_sub.empty()){
vector<ll> d=dp_sub.front();
dp[d[0]][d[1]]=d[2];
dp_sub.PF();
}
for(auto i=cand.begin();i!=cand.end();i++){
now.PB(*i);
}
bfs(d+1);
}
signed main(){
//Code zur Beschleunigung der Eingabe
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> h >> w >>k;
ll x1,y1,x2,y2;cin >> x1 >> y1 >> x2 >> y2;
vector<string> c(h);REP(i,h)cin >> c[i];
dp.resize(h);
REP(i,h){
REP(j,w){
if(c[i][j]=='.')dp[i].PB(INF);
else dp[i].PB(-1);
}
}
now.PB(MP(x1-1,y1-1));
dp[x1-1][y1-1]=0;
bfs(1);
if(dp[x2-1][y2-1]!=INF) cout << dp[x2-1][y2-1] << endl;
else cout << -1 << endl;
}
Recommended Posts