This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
const int lim=1e3;
typedef pair<int,int> ii;
int n,m,S,T,d[30005][1005];
bool Visited[30005],Free[30005][1005];
map<int,int> dd[30005];
map<int,bool> FFree[30005];
vector<int> g[30005];
queue<ii> Q;
int main()
{
ios_base::sync_with_stdio(false);
//freopen("TEST.INP","r",stdin);
cin>>n>>m;
int pos,step;
for(int i=1;i<=m;i++)
{
cin>>pos>>step;
g[pos+1].push_back(step);
if(i==1)
S=pos+1;
if(i==2)
T=pos+1;
}
for(int i=0; i<g[S].size(); i++)
{
if(g[S][i]<=lim)
Free[S][g[S][i]]=true;
else
FFree[S][g[S][i]]=true;
Q.push(ii(S,g[S][i]));
}
while(Q.size()>0)
{
int u=Q.front().first;
int v=Q.front().second;
int w;
if(v<=lim)
w=d[u][v];
else
w=dd[u][v];
Q.pop();
if(u==T)
{
cout<<w;
return 0;
}
if(Visited[u]==false)
{
Visited[u]=true;
for(int i=0; i<g[u].size(); i++)
{
if(u-g[u][i]>=1)
{
if(g[u][i]<=lim&&Free[u-g[u][i]][g[u][i]]==false)
{
Free[u-g[u][i]][g[u][i]]=true;
d[u-g[u][i]][g[u][i]]=w+1;
Q.push(ii(u-g[u][i],g[u][i]));
}
else
if(g[u][i]>lim&&FFree[u-g[u][i]][g[u][i]]==false)
{
FFree[u-g[u][i]][g[u][i]]=true;
dd[u-g[u][i]][g[u][i]]=w+1;
Q.push(ii(u-g[u][i],g[u][i]));
}
}
if(u+g[u][i]<=n)
{
if(g[u][i]<=lim&&Free[u+g[u][i]][g[u][i]]==false)
{
Free[u+g[u][i]][g[u][i]]=true;
d[u+g[u][i]][g[u][i]]=w+1;
Q.push(ii(u+g[u][i],g[u][i]));
}
else
if(g[u][i]>lim&&FFree[u+g[u][i]][g[u][i]]==false)
{
FFree[u+g[u][i]][g[u][i]]=true;
dd[u+g[u][i]][g[u][i]]=w+1;
Q.push(ii(u+g[u][i],g[u][i]));
}
}
}
}
if(u-v>=1)
{
if(v<=lim&&Free[u-v][v]==false)
{
Free[u-v][v]=true;
d[u-v][v]=w+1;
Q.push(ii(u-v,v));
}
else
if(v>lim&&FFree[u-v][v]==false)
{
FFree[u-v][v]=true;
dd[u-v][v]=w+1;
Q.push(ii(u-v,v));
}
}
if(u+v<=n)
{
if(v<=lim&&Free[u+v][v]==false)
{
Free[u+v][v]=true;
d[u+v][v]=w+1;
Q.push(ii(u+v,v));
}
else
if(v>lim&&FFree[u+v][v]==false)
{
FFree[u+v][v]=true;
dd[u+v][v]=w+1;
Q.push(ii(u+v,v));
}
}
}
cout<<-1;
}
Compilation message (stderr)
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:28:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<g[S].size(); i++)
~^~~~~~~~~~~~
skyscraper.cpp:54:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0; i<g[u].size(); i++)
~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |