#!/bin/python3 import sys #while we didn't reach (0,0) or (no new squares are reachables): # look at squares that we could reach from the last discovered ones # substract those that we already discovered in previous steps (which means less moves) # store these new squares in a set, named new set #if (0,0) is in the new set, then print the number of iterations over the while loop #else print(-1) n = int(input().strip()) # your code goes here board=[] for i in range(n): for j in range(n): board.append([i,j]) #print(board) zero=[0,0] reached=[[n-1,n-1]] for i in range(1,n): ans=[] for j in range(1,n): reached=[[n-1,n-1]] reachable=[] #print("New Knight:",i,j) moves=[ [i,j], [i,-j] , [-i,j], [-i,-j], [j,i], [j,-i], [-j,i], [-j,-i] ] for square in reached: for move in moves: newsquare=[square[0]+move[0],square[1]+move[1]] if newsquare in board: reachable.append(newsquare) #print("Initial Reachable:",reachable) movecount = 1 while (zero not in reachable) and len(reachable)>0 and (movecount < 100): newreachable=[] for square in reachable: for move in moves: newsquare=[square[0]+move[0],square[1]+move[1]] if newsquare in board: if newsquare not in newreachable: newreachable.append(newsquare) #print("Reachable this move:",newreachable) #print("Previously Reached:",reached) for x in reached: if x in newreachable: newreachable.remove(x) #print("New reachable this move",newreachable) for x in newreachable: reached.append(x) #print("New total reached",reached) reachable=newreachable.copy() movecount+=1 #print("After",movecount,"Moves") #print("len reachable =",len(reachable)) #print("zero not in reachable:",zero not in reachable) if zero in reachable: #print(i,j,"reached zero in",movecount,"moves") ans.append(movecount) if len(reachable)==0: #print(i,j,"failed to reach zero") ans.append(-1) for x in ans: print(x,end=' ') print()