#!/bin/python3 import sys from collections import deque class Board(object): def __init__(self, i, j, n): assert n > 0 and 0 < i < n and 0 < j < n self.N = n self.I = i self.J = j def next_pos(self, x, y): assert 0 <= x < self.N and 0 <= y < self.N i = self.I j = self.J out = set() for _i in i, -i: for _j in j, -j: nx = x + _i ny = y + _j if 0 <= nx < self.N and 0 <= ny < self.N: out.add((nx, ny)) nx = x + _j ny = y + _i if 0 <= nx < self.N and 0 <= ny < self.N: out.add((nx, ny)) return list(out) class BFS(object): def __init__(self, board): self.N = board.N self.board = board self.x_start = 0 self.y_start = 0 self.x_end = self.N - 1 self.y_end = self.N - 1 def search(self): x = self.x_start y = self.y_start visited = set() queue = deque([(x, y, 0)]) while len(queue) > 0: x, y, level = queue.popleft() if (x, y) in visited: continue if (x, y) == (self.x_end, self.y_end): return level for (next_x, next_y) in self.board.next_pos(x, y): queue.append((next_x, next_y, level + 1)) visited.add((x, y)) # Path is not found return -1 n = int(input().strip()) # your code goes here #step = BFS(Board(1, 3, n)).search() #print(step) buffer = {} for i in range(1, n): for j in range(1, n): if j >= i: step = BFS(Board(i, j, n)).search() print(step, end=' ') if j > i: buffer[(j, i)] = step else: print(buffer[(i, j)], end=' ') print('')