#!/bin/python import sys n = int(raw_input().strip()) # calculate all combinations of a,b pairs = [] goal = n-1 memo = {} for a in range(1, n): for b in range(1, n): if (a,b) in memo: print memo[(a, b)], continue # Elements: (x, y, moves) queue = [] queue.append((0, 0, 0)) explored = {} output = -1 while len(queue) > 0: curr = queue.pop(0) x = curr[0] y = curr[1] moves = curr[2] # explore this position if x == goal and y == goal: output = moves break # add next layer of positions to the queue # dfs will check each of the 8 move choices #x1+a, x1-a, x1+b, x1-b next_move = moves+1 # needs to check if a move will be in the boundaries and not to a previously explored space if x + a < n: if y + b < n: if (x+a, y+b) not in explored: queue.append((x+a, y+b, next_move)) explored[(x+a, y+b)] = True if y - b >= 0: if (x+a, y-b) not in explored: queue.append((x+a, y-b, next_move)) explored[(x+a, y-b)] = True if x - a >= 0: if y + b < n: if (x-a, y+b) not in explored: queue.append((x-a, y+b, next_move)) explored[(x-a, y+b)] = True if y - b >= 0: if (x-a, y-b) not in explored: queue.append((x-a, y-b, next_move)) explored[(x-a, y-b)] = True if x + b < n: if y + a < n: if (x+b, y+a) not in explored: queue.append((x+b, y+a, next_move)) explored[(x+b, y+a)] = True if y - a >= 0: if (x+b, y-a) not in explored: queue.append((x+b, y-a, next_move)) explored[(x+b, y-a)] = True if x - b >= 0: if y + a < n: if (x-b, y+a) not in explored: queue.append((x-b, y+a, next_move)) explored[(x-b, y+a)] = True if y - a >= 0: if (x-b, y-a) not in explored: queue.append((x-b, y-a, next_move)) explored[(x-b, y-a)] = True print output, memo[(a, b)] = output print ""