#include <iostream> #include <vector> #include <algorithm> #include <stack> #include <queue> #include <map> using namespace std; int main() { int n; cin >> n; int x1 = 1, x2 = n, y1 = 1, y2 = n; for (int a = 1; a < n; a++) { for (int b = 1; b < n; b++) { bool flag = 0; vector<vector<bool>> used(2 * n, vector<bool>(2 * n)); vector<vector<int>> d(2 * n, vector<int>(2 * n)); vector<vector<pair<int, int>>> prev(2 * n, vector<pair<int, int>>(2 * n)); queue<pair<int, int>> q; q.push(make_pair(x1, y1)); d[x1][y1] = 0; used[x1][y1] = 1; while (q.size() != 0) { int x, y; x = q.front().first; y = q.front().second; q.pop(); if (x + a <= n && x + a >= 1 && y + b >= 1 && y + b <= n && !used[x + a][y + b]) { used[x + a][y + b] = 1; d[x + a][y + b] = d[x][y] + 1; prev[x + a][y + b] = make_pair(x, y); q.push(make_pair(x + a, y + b)); if (x + a == x2 && y + b == y2) { cout << d[x][y] + 1 << ' '; flag = 1; } } if (x + a <= n && x + a >= 1 && y - b >= 1 && y - b <= n && !used[x + a][y - b]) { used[x + a][y - b] = 1; d[x + a][y - b] = d[x][y] + 1; prev[x + a][y - b] = make_pair(x, y); q.push(make_pair(x + a, y - b)); if (x + a == x2 && y - b == y2) { cout << d[x][y] + 1 << ' '; flag = 1; } } if (x - a <= n && x - a >= 1 && y + b >= 1 && y + b <= n && !used[x - a][y + b]) { used[x - a][y + b] = 1; d[x - a][y + b] = d[x][y] + 1; prev[x - a][y + b] = make_pair(x, y); q.push(make_pair(x - a, y + b)); if (x - a == x2 && y + b == y2) { cout << d[x][y] + 1 << ' '; flag = 1; } } if (x - a <= n && x - a >= 1 && y - b >= 1 && y - b <= n && !used[x - a][y - b]) { used[x - a][y - b] = 1; d[x - a][y - b] = d[x][y] + 1; prev[x - a][y - b] = make_pair(x, y); q.push(make_pair(x - a, y - b)); if (x - a == x2 && y - b == y2) { cout << d[x][y] + 1 << ' '; flag = 1; } } if (x + b <= n && x + b >= 1 && y + a >= 1 && y + a <= n && !used[x + b][y + a]) { used[x + b][y + a] = 1; d[x + b][y + a] = d[x][y] + 1; prev[x + b][y + a] = make_pair(x, y); q.push(make_pair(x + b, y + a)); if (x + b == x2 && y + a == y2) { cout << d[x][y] + 1 << ' '; flag = 1; } } if (x + b <= n && x + b >= 1 && y - a >= 1 && y - a <= n && !used[x + b][y - a]) { used[x + b][y - a] = 1; d[x + b][y - a] = d[x][y] + 1; prev[x + b][y - a] = make_pair(x, y); q.push(make_pair(x + b, y - a)); if (x + b == x2 && y - a == y2) { cout << d[x][y] + 1 << ' '; flag = 1; } } if (x - b <= n && x - b >= 1 && y + a >= 1 && y + a <= n && !used[x - b][y + a]) { used[x - b][y + a] = 1; d[x - b][y + a] = d[x][y] + 1; prev[x - b][y + a] = make_pair(x, y); q.push(make_pair(x - b, y + a)); if (x - b == x2 && y + a == y2) { cout << d[x][y] + 1 << ' '; flag = 1; } } if (x - b <= n && x - b >= 1 && y - a >= 1 && y - a <= n && !used[x - b][y - a]) { used[x - b][y - a] = 1; d[x - b][y - a] = d[x][y] + 1; prev[x - b][y - a] = make_pair(x, y); q.push(make_pair(x - b, y - a)); if (x - b == x2 && y - a == y2) { cout << d[x][y] + 1 << ' '; flag = 1; } } } if (!flag) { cout << -1 << ' '; } } cout << endl; } }