#!/bin/python import sys from collections import deque # breadth first search def is_path(start, MOVEs, n): node_queue = deque() node_queue.appendleft(start) visited_nodes = set([start]) depth = 0 next_layer_node_number = 0 current_layer_node_number = 1 valid_nodes = [start] while node_queue: current_node = node_queue.pop() #print 'I am looking at node: ', current_node #print 'depth: ', depth #print 'current node_queue: ', node_queue, '\n' for mov in MOVEs: next_x = current_node[0] + mov[0] next_y = current_node[1] + mov[1] if next_x >= 0 and next_x < n and next_y >= 0 and next_y < n: # print 'current_move: ', next_x, next_y if next_x == n-1 and next_y == n-1: depth += 1 return depth if (next_x, next_y) not in visited_nodes: visited_nodes.add((next_x, next_y)) if current_layer_node_number != 0: next_layer_node_number += 1 node_queue.appendleft((next_x, next_y)) valid_nodes.append((next_x, next_y)) current_layer_node_number -= 1 if current_layer_node_number == 0: # print 'current_layer_node_number==0, depth:', depth # print 'next_layer_node_number: ', next_layer_node_number, '\n\n' if len(valid_nodes) == 0: return -1 depth += 1 current_layer_node_number = next_layer_node_number next_layer_node_number = 0 valid_nodes = [] return -1 def list_moves(i, j): r = set([(i, j), (i, -j), (-i, j), (-i, -j), (j, i), (j, -i), (-j, i), (-j, -i)]) return r n = int(raw_input().strip()) # your code goes here min_move = [[-1 for i in range(n-1)] for j in range(n-1)] for i in range(1, n): for j in range(i, n): min_move[i-1][j-1] = str(is_path((0,0), list_moves(i, j), n)) min_move[j-1][i-1] = min_move[i-1][j-1] for i in range(n-1): print ' '.join(min_move[i])