#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; struct point { public: int r;int c; point(int r, int c) :r(r),c(c) {} friend bool operator<(point a, point b) { if (a.r == b.r) return (a.c > b.c); if (a.r > b.r) return true; else return false; } }; int addPoint(int n, int row, int col, point & p) { if (row < 0 || col < 0 || row >= n || col >= n ) return -1; p = point(row, col); return 0; } void addPoints(int n, int row, int col, int i, int j, set & pts) { point p(0,0); if (addPoint(n, row + i, col + j, p) == 0) { pts.insert(p); } if (addPoint(n, row + i, col - j, p) == 0) { pts.insert(p); } if (addPoint(n, row - i, col + j, p) == 0) { pts.insert(p); } if (addPoint(n, row - i, col - j, p) == 0) { pts.insert(p); } if (addPoint(n, row + j, col + i, p) == 0) { pts.insert(p); } if (addPoint(n, row + j, col - i, p) == 0) { pts.insert(p); } if (addPoint(n, row - j, col + i, p) == 0) { pts.insert(p); } if (addPoint(n, row - j, col - i, p) == 0) { pts.insert(p); } } int getMinimumMoves(int n, int i, int j) { set travelledPoints; set activePoints; activePoints.insert(point(n - 1, n - 1)); int moves = 0; while (activePoints.find(point(0,0))== activePoints.end()) { set tmp; for (const auto& c : activePoints) addPoints(n, c.r, c.c, i, j, tmp); for (const auto& c : travelledPoints) { if (tmp.find(c) != tmp.end()) tmp.erase(c); } for (const auto& c : activePoints) travelledPoints.insert(c); activePoints.clear(); activePoints = tmp; if (activePoints.size() <= 0) { moves = -1; break; } moves++; } return moves; } int main() { int n; cin >> n; map pts; for (int i = 1; i < n; i++) { for (int j = 1; j < n; j++) { int moves = -1; if (pts.find(point(j,i)) != pts.end()) moves = pts[point(j,i)]; else moves = getMinimumMoves(n, i, j); pts[point(i, j)] = moves; cout << moves << " "; } cout << endl; } return 0; }