We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Java with optimisations: do only half, as output is symmetrical, special cases i==j, greatest common factor of i,j does not divide n-1.
importjava.io.*;importjava.math.*;importjava.security.*;importjava.text.*;importjava.util.*;importjava.util.concurrent.*;importjava.util.function.*;importjava.util.regex.*;importjava.util.stream.*;importstaticjava.util.stream.Collectors.joining;importstaticjava.util.stream.Collectors.toList;classResult{/* * Complete the 'knightlOnAChessboard' function below. * * The function is expected to return a 2D_INTEGER_ARRAY. * The function accepts INTEGER n as parameter. */publicstaticint[][]states;publicstaticint[]tmp;publicstaticintgcf(inti,intj){intk=(i>j)?j:i;intm=(i>j)?i:j;while(k>1){intq=m-k;if(q==0){returnk;}if(q==1){return1;}if(q>k){m=q;}else{intw=k;k=q;m=w;}}returnk;}publicstaticIntegerket(inti,intj,intd){returni*65536+j*256+d;}publicstaticvoidfromk(Integerk){inta=k/65536;intb=(k-a*65536)/256;intc=k-a*65536-b*256;tmp[0]=a;tmp[1]=b;tmp[2]=c;}publicstaticvoidsetstates(inti,intj){states[0][0]=-i;states[0][1]=-j;states[1][0]=-i;states[1][1]=j;states[2][0]=i;states[2][1]=-j;states[3][0]=i;states[3][1]=j;states[4][0]=-j;states[4][1]=-i;states[5][0]=-j;states[5][1]=i;states[6][0]=j;states[6][1]=-i;states[7][0]=j;states[7][1]=i;}publicstaticbooleancheckpos(intx,inty,intn){return(x>=0&&y>=0&&x<n&&y<n);}publicstaticIntegergetk(inti,intj){returni*256+j;}publicstaticintbfs(inti,intj,intn){Set<Integer>seen=newHashSet<>();Queue<Integer>todo=newLinkedList<>();todo.add(ket(0,0,0));seen.add(getk(0,0));while(!todo.isEmpty()){fromk(todo.remove());intx=tmp[0];inty=tmp[1];intd=tmp[2];if(x==n-1&&y==n-1){returnd;}for(intq=0;q<8;q++){intxx=x+states[q][0];intyy=y+states[q][1];if(checkpos(xx,yy,n)){Integerkk=getk(xx,yy);if(!seen.contains(kk)){seen.add(getk(xx,yy));todo.add(ket(xx,yy,d+1));}}}}return-1;}publicstaticList<List<Integer>>knightlOnAChessboard(intn){// BFS.tmp=newint[3];// Since output is symmetrical, do upper half:states=newint[8][2];int[][]resulti=newint[n][n];for(inti=1;i<n;i++){for(intj=i;j<n;j++){// optimize if i==jif(i==j&&((n-1)%i==0||i==1)){resulti[i][j]=(n-1)/i;}else{intf=gcf(i,j);// optimize greatest common factor cannot reach (n-1, n-1):if(f!=1&&(n-1)%f!=0){resulti[i][j]=-1;}else{setstates(i,j);resulti[i][j]=bfs(i,j,n);}}}}// Since output is symmetrical, copy upper half to lower half:List<List<Integer>>result=newArrayList<>();for(inti=1;i<n;i++){List<Integer>row=newArrayList<>();for(intj=1;j<n;j++){intx=(i>j)?i:j;inty=(i>j)?j:i;row.add(resulti[y][x]);}result.add(row);}returnresult;}}publicclassSolution{publicstaticvoidmain(String[]args)throwsIOException{BufferedReaderbufferedReader=newBufferedReader(newInputStreamReader(System.in));BufferedWriterbufferedWriter=newBufferedWriter(newFileWriter(System.getenv("OUTPUT_PATH")));intn=Integer.parseInt(bufferedReader.readLine().trim());List<List<Integer>>result=Result.knightlOnAChessboard(n);result.stream().map(r->r.stream().map(Object::toString).collect(joining(" "))).map(r->r+"\n").collect(toList()).forEach(e->{try{bufferedWriter.write(e);}catch(IOExceptionex){thrownewRuntimeException(ex);}});bufferedReader.close();bufferedWriter.close();}}
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
KnightL on a Chessboard
You are viewing a single comment's thread. Return to all comments →
Java with optimisations: do only half, as output is symmetrical, special cases i==j, greatest common factor of i,j does not divide n-1.