#!/bin/python import sys def destnation_reached(been_to): for move in been_to: if move[0] == move[1] and move[1] == n-1: return True return False def trim_to_legal_move(moves, length): k=0 while k < len(moves): if moves[k][0]<0 or moves[k][1]<0 or moves[k][0]>n-1 or moves[k][1]>n-1: moves.remove(moves[k]) k-=1 k+=1 return moves n = int(raw_input().strip()) # your code goes here destination = [n-1, n-1] answer_Matrix = [[0 for x in range(n-1)] for y in range(n-1)] for i in range(1,n): for j in range(i, n): step_count = 0 been_to = [[0,0]] can_go = [[0,0]] MissionComplete = False while not MissionComplete and len(can_go)>0: #For every potential Moves, I need to update the new potential moves pot_mov = [] for move in can_go: if i == j: pot_mov.extend ([[move[0]+i, move[1]+j], [move[0]-i, move[1]-j], [move[0]+i, move[1]-j], [move[0]-i, move[1]+j]]) else: pot_mov.extend ([[move[0]+i, move[1]+j], [move[0]+j, move[1]+i], [move[0]-i, move[1]-j], [move[0]-j, move[1]-i], [move[0]+i, move[1]-j], [move[0]+j, move[1]-i], [move[0]-i, move[1]+j], [move[0]-j, move[1]+i]]) pot_mov = trim_to_legal_move(pot_mov, len(pot_mov)) #Add new moves only if it is not yet in been_to temp_list = [] for move in pot_mov: if move not in been_to: been_to.append(move) temp_list.append(move) #update can_go can_go = temp_list #Knight took one more step and is able to reach places in been_to step_count+=1 #Check if the knight is able to reach the destination MissionComplete = destnation_reached(been_to) if MissionComplete: answer_Matrix[i-1][j-1] = step_count answer_Matrix[j-1][i-1] = step_count else: answer_Matrix[i-1][j-1] = -1 answer_Matrix[j-1][i-1] = -1 for i in range(n-1): for j in range(n-1): sys.stdout.write(str(answer_Matrix[i][j]) + " ") print ""