This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
import java.io.*;
import java.util.*;
public class obelisk {
static long MAX=(long)1e9+5;
static int K,IEND,JEND;
static long INF=(long)1e18;
static HashSet<Long>[]holes;
static long dist(int i1,int j1,int i2,int j2) {
int dx=Math.abs(i1-i2),dy=Math.abs(j1-j2);
if(K==2) {
return dx+dy;
}
return Math.min(dist(dx,dy), dist(dy,dx));
}
static long dist(int dx,int dy) {
if(dy%K!=0)
return INF;
long ans=dy/K*2;
ans+=dx/K*2;
if(dx%K>0) {
ans+=dx%K;
if(dy==0)
ans+=2;
}
return ans;
}
static long hash(int i,int j) {
return i*MAX+j;
}
static long dp(int floor,int i,int j) {
long hash=hash(i,j);
long ans=INF;
if(floor==0) {
ans=dist(i, j, IEND, JEND);
}
else {
if(holes[floor].contains(hash))
ans=dp(floor-1,i,j);
else
{
for(long hole:holes[floor]) {
int i2=(int) (hole/MAX),j2=(int) (hole%MAX);
ans=Math.min(ans,dp(floor-1,i2,j2)+dist(i, j, i2, j2));
}
}
}
return ans;
}
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner();
PrintWriter out = new PrintWriter(System.out);
int n=sc.nextInt();
K=sc.nextInt()+1;
int sx=sc.nextInt(),sy=sc.nextInt();
IEND=sc.nextInt();
JEND=sc.nextInt();
holes=new HashSet[n];
for(int floor=n-1;floor>0;floor--) {
int h=sc.nextInt();
holes[floor]=new HashSet();
while(h-->0) {
int i=sc.nextInt(),j=sc.nextInt();
long x=hash(i,j);
holes[floor].add(x);
}
}
long ans=dp(n-1, sx, sy);
out.print(ans>=INF?-1:ans);
out.close();
}
static class Scanner {
BufferedReader br;
StringTokenizer st;
Scanner() {
br = new BufferedReader(new InputStreamReader(System.in));
}
Scanner(String fileName) throws FileNotFoundException {
br = new BufferedReader(new FileReader(fileName));
}
String next() throws IOException {
while (st == null || !st.hasMoreTokens())
st = new StringTokenizer(br.readLine());
return st.nextToken();
}
String nextLine() throws IOException {
return br.readLine();
}
int nextInt() throws IOException {
return Integer.parseInt(next());
}
long nextLong() throws NumberFormatException, IOException {
return Long.parseLong(next());
}
double nextDouble() throws NumberFormatException, IOException {
return Double.parseDouble(next());
}
boolean ready() throws IOException {
return br.ready();
}
}
}
Compilation message (stderr)
Note: obelisk.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
# | 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... |