#include #include #include #include #include #include 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> used(2 * n, vector(2 * n)); vector> d(2 * n, vector(2 * n)); vector>> prev(2 * n, vector>(2 * n)); queue> 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; } }