#!/bin/python import sys import itertools n = int(raw_input().strip()) # your code goes here def is_goal(n, pos): return pos[0] == n-1 and pos[1] == n-1 def get_successors(n, i, j, pos, move_number): successors = [] pos_i = [i, -i] pos_j = [j, -j] possible_moves = itertools.product(pos_i, pos_j) for move in possible_moves: i, j = move new_pos = (pos[0] + i, pos[1] + j) if new_pos[0] < n and new_pos[1] < n and new_pos[0] >= 0 and new_pos[1] >= 0: successors.append((new_pos, move_number+1)) successors.append(((new_pos[1], new_pos[0]), move_number+1)) return successors cache = {} def shortest_path_search(n, i, j): if frozenset([i, j]) not in cache: frontier = [((0, 0), 0)] visited = set() while len(frontier): position, number = frontier.pop(0) if position not in visited: visited.add(position) if is_goal(n, position): cache[frozenset([i,j])] = number return number else: frontier += get_successors(n, i, j, position, number) cache[frozenset([i,j])] = -1 return -1 else: return cache[frozenset([i,j])] def print_all_moves(n): for i in range(1, n): for j in range(1, n): print shortest_path_search(n, i, j), print print_all_moves(n)