#!/bin/python3 import sys import math n = int(input().strip()) # your code goes here def valid_moves(n, knight, cur_pos): i, j = knight moves = [(i,j), (j, i), (i, -j), (-i, j), (-i, -j), (j, -i), (-j, i), (-j, -i)] res = [] for move in moves: loc = (cur_pos[0] + move[0], cur_pos[1] + move[1]) if loc[0] >= 0 and loc[0] < n and loc[1] >= 0 and loc[1] < n: res.append(move) return res def min_moves(n, knight): cur_pos = (0, 0) goal = (n-1, n-1) moves_queue = [cur_pos] dist = {} dist[cur_pos] = 0 while len(moves_queue): #print(moves_queue) cur_pos = moves_queue.pop(0) if cur_pos == goal: return dist[goal] for move in valid_moves(n, knight, cur_pos): new_pos = (cur_pos[0] + move[0], cur_pos[1] + move[1]) if new_pos not in dist: dist[new_pos] = dist[cur_pos] + 1 moves_queue.append(new_pos) return -1 def array2str(arr): res_str = "" for row in arr: for num in row: res_str += str(num) + " " res_str += "\n" return res_str def anwser(n): results = [[float('nan') for i in range(0, n-1)] for row in range(0, n-1)] for i in range(len(results)): for j in range(len(results[0])): # heuristic, if i == j, than result is (n-1) / i if i == j: move = i + 1 if (n-1) % move == 0: results[i][i] = (n-1) // move else: results[i][i] = -1 # i != j, result not found yet if math.isnan(results[i][j]): results[i][j] = min_moves(n, (i+1,j+1)) return results anwser_str = array2str(anwser(n)) print(anwser_str)