#include #include #include #include #include using namespace std; using mat2 = vector>; int N; struct pt { int x; int y; inline pt add(pt a) { return {x + a.x, y + a.y}; } inline bool isOut() const { return x < 0 || x >= N || y < 0 || y >= N; } inline bool operator==(const pt &rhs) const { return std::tie(x, y) == std::tie(rhs.x, rhs.y); } }; inline int min(int a, int b) { return (a < b) ? a : b; } inline int dist(pt pos, const pt &to, const pt &move, mat2 &distMap, int moves = 0) { if (pos.isOut()) return numeric_limits::max(); if (moves >= distMap[pos.x][pos.y]) return numeric_limits::max(); if (pos == to) return moves; distMap[pos.x][pos.y] = moves; int minDist = numeric_limits::max(); minDist = min(minDist, dist(pos.add({ move.x, move.y}), to, move, distMap, moves + 1)); minDist = min(minDist, dist(pos.add({ move.y, move.x}), to, move, distMap, moves + 1)); minDist = min(minDist, dist(pos.add({ move.x, -move.y}), to, move, distMap, moves + 1)); minDist = min(minDist, dist(pos.add({-move.x, move.y}), to, move, distMap, moves + 1)); minDist = min(minDist, dist(pos.add({ move.y, -move.x}), to, move, distMap, moves + 1)); minDist = min(minDist, dist(pos.add({-move.y, move.x}), to, move, distMap, moves + 1)); minDist = min(minDist, dist(pos.add({-move.x, -move.y}), to, move, distMap, moves + 1)); minDist = min(minDist, dist(pos.add({-move.y, -move.x}), to, move, distMap, moves + 1)); return minDist; } int main() { cin >> N; // N = 5; // mat2 distMap(N, vector(N, numeric_limits::max())); // cout << dist({0, 0}, {4, 4}, {1, 2}, distMap) << endl; mat2 R(N, vector(N, 0)); // Compute mat2 distMap(N, vector(N, numeric_limits::max())); for (int i = 1; i < N; ++i) { for (int j = 1; j <= i; ++j) { for (auto &sub : distMap) { sub.clear(); sub.resize(N, numeric_limits::max()); } int d = dist({0, 0}, {N - 1, N - 1}, {i, j}, distMap); R[i][j] = (d == numeric_limits::max()) ? -1 : d; } } // Display for (int i = 1; i < N; ++i) { for (int j = 1; j < N; ++j) { if (j > 1) cout << ' '; cout << ((i > j) ? R[i][j] : R[j][i]); } cout << '\n'; } cout << flush; return 0; }