#!/bin/python3 import sys n = int(input().strip()) # your code goes here def get_moves(p, d): # return all moves from point moves = set() for i in (d[0], -d[0]): for j in (d[1], -d[1]): x = p[0] + i y = p[1] + j move = (x, y) if 0 <= x < n and 0 <= y < n: moves.add((x, y)) return moves def make_move(p, d): m1 = get_moves(p, d) m2 = get_moves(p, d[::-1]) poss = set.union(m1, m2) return poss def get_to(init, dest, step): history = set() c = 0 history.add(init) obs = [(init, c)] while obs: point, cost = obs.pop(0) # print("Point: ", point, cost) np = make_move(point, step) for p in np: if p == dest: return cost + 1 if not p in history: history.add(p) obs.append((p, cost + 1)) return -1 def build_matrix(n): init = (0, 0) dest = (n-1, n-1) res = [[None for i in range(n-1)] for j in range(n-1)] for i in range(1, n): for j in range(1, i + 1): step = (i, j) cost = get_to(init, dest, step) # print(" with: ", step, " ==== Get point in ", cost, " steps") res[i-1][j-1] = cost res[j-1][i-1] = cost for x in res: line = " ".join([str(y) for y in x]) print(line) def test(num): from timeit import default_timer as timer t = timer() for i in range(num): build_matrix(n) print(timer() - t) build_matrix(n) # test(10)