#!/bin/python import sys def getMoves(a,b): moves = [] moves.append([ a, b]) moves.append([ a, -b]) moves.append([-a, b]) moves.append([-a, -b]) moves.append([ b, a]) moves.append([ b, -a]) moves.append([-b, a]) moves.append([-b, -a]) return moves def getFrontier(i,j,moves,n,visited): frontier = [] atCorner = 0 k = 0 for m in moves: if (i + m[0] < n and i + m[0] >= 0\ and j + m[1] < n and j + m[1] >= 0): if visited.has_key(n * (i + m[0]) + j + m[1]): pass else: frontier.append([i + m[0],j + m[1]]) visited[n*(i + m[0]) + j + m[1]] = 1 if (frontier[k][0] == n - 1 and frontier[k][1] == n - 1): atCorner = 1 k += 1 return frontier, atCorner n = int(raw_input().strip()) totalMoves = [] for i in range(1,n): thisRowMoves = [] for j in range(1,n): currentFrontier = [[0,0]] # We want to keep track of squares we already # visited. Number the squares from the top right # corner as n * i + j visitedSquares = dict([]) visitedSquares[0] = 1 x = 0 y = 0 atCorner = 0 nMoves = 0 moves = getMoves(i,j) while (atCorner == 0 and nMoves < 1000): newFrontier = [] nMoves += 1 for p in currentFrontier: f, corner = getFrontier(p[0],p[1],moves,n,visitedSquares) newFrontier += f if (corner == 1): atCorner = 1 #print newFrontier currentFrontier = newFrontier; if (nMoves == 1000): nMoves = -1 thisRowMoves.append(nMoves) #print visitedSquares totalMoves.append(thisRowMoves) for rawLine in totalMoves: outStr = "" for val in rawLine: outStr += str(val) + " " print outStr