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 "walk.h"
#include <bits/stdc++.h>
#include <cstdio>
#include <cassert>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=1000+1;
const double eps=1e-5;
const int mo=1e9+7;
int n,m,s,g;
int xx[N],h[N];
int yy[N];
struct edge {
int l,r;
ll y;
} e[N];
bool a[N][N];
int d[N][N];
struct point {
int x,y;
};
queue<point> q;
bool ok_l[N][N],ok_r[N][N];
bool ok(int x,int y) {
if (x<0||y<0) return 0;
return 1;
}
void bfs() {
d[xx[s]][0]=0;
q.push(point{xx[s],0});
while (!q.empty()) {
int x=q.front().x,y=q.front().y;
q.pop();
REP(i,-1,1) REP(j,-1,1) if (i==0&&j||i&&j==0) {
if (i==-1&&!ok_l[x][y]) continue;
if (i==1&&!ok_r[x][y]) continue;
if (ok(x+i,y+j)&&a[x+i][y+j]&&d[x+i][y+j]==inf) {
d[x+i][y+j]=d[x][y]+1;
//cout<<x<<" "<<y<<" "<<d[x][y]<<endl;
q.push(point{x+i,y+j});
}
}
}
}
long long min_distance(std::vector<int> X, std::vector<int> H, std::vector<int> L, std::vector<int> R, std::vector<int> Y, int ss, int gg) {
s=ss+1;
g=gg+1;
n=X.size(),m=Y.size();
FOR(i,n) xx[i]=X[i-1],h[i]=H[i-1];
FOR(i,m) e[i].l=L[i-1]+1,e[i].r=R[i-1]+1,e[i].y=Y[i-1];
FOR(i,n) {
int hh=h[i];
REP(j,0,hh) a[xx[i]][j]=1;
}
FOR(i,m) {
int l=e[i].l,r=e[i].r,y=e[i].y;
REP(j,xx[l],xx[r]) a[j][y]=1;
REP(j,xx[l],xx[r]-1) ok_r[j][y]=1;
REP(j,xx[l]+1,xx[r]) ok_l[j][y]=1;
}
memset(d,0x3f,sizeof (d));
bfs();
ll ans=d[xx[g]][0];
if (ans>10000) ans=-1;
return ans;
}
Compilation message (stderr)
walk.cpp: In function 'void bfs()':
walk.cpp:47:35: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
47 | REP(i,-1,1) REP(j,-1,1) if (i==0&&j||i&&j==0) {
| ~~~~^~~
# | 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... |