#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 Node { int x; int y; int step; Node(int x, int y, int step) : x(x), y(y), step(step) {} }; int getSteps(int n, int i, int j) { if (i == j) { if ((n - 1) % i != 0) return -1; return (n - 1) / i; } vector> visited(n, vector(n)); queue q; q.push(new Node(0, 0, 0)); visited[0][0] = true; while (!q.empty()) { Node* curr = q.front(); q.pop(); if (curr->x == n - 1 && curr->y == n - 1) { int step = curr->step; delete curr; return step; } if (curr->x + i < n && curr->y + j < n && !visited[curr->x + i][curr->y + j]) { visited[curr->x + i][curr->y + j] = true; q.push(new Node(curr->x + i, curr->y + j, curr->step + 1)); } if (curr->x + i < n && curr->y - j >= 0 && !visited[curr->x + i][curr->y - j]) { visited[curr->x + i][curr->y - j] = true; q.push(new Node(curr->x + i, curr->y - j, curr->step + 1)); } if (curr->x - i >= 0 && curr->y + j < n && !visited[curr->x - i][curr->y + j]) { visited[curr->x - i][curr->y + j] = true; q.push(new Node(curr->x - i, curr->y + j, curr->step + 1)); } if (curr->x - i >= 0 && curr->y - j >= 0 && !visited[curr->x - i][curr->y - j]) { visited[curr->x - i][curr->y - j] = true; q.push(new Node(curr->x - i, curr->y - j, curr->step + 1)); } if (i != j) { swap(i, j); if (curr->x + i < n && curr->y + j < n && !visited[curr->x + i][curr->y + j]) { visited[curr->x + i][curr->y + j] = true; q.push(new Node(curr->x + i, curr->y + j, curr->step + 1)); } if (curr->x + i < n && curr->y - j >= 0 && !visited[curr->x + i][curr->y - j]) { visited[curr->x + i][curr->y - j] = true; q.push(new Node(curr->x + i, curr->y - j, curr->step + 1)); } if (curr->x - i >= 0 && curr->y + j < n && !visited[curr->x - i][curr->y + j]) { visited[curr->x - i][curr->y + j] = true; q.push(new Node(curr->x - i, curr->y + j, curr->step + 1)); } if (curr->x - i >= 0 && curr->y - j >= 0 && !visited[curr->x - i][curr->y - j]) { visited[curr->x - i][curr->y - j] = true; q.push(new Node(curr->x - i, curr->y - j, curr->step + 1)); } } delete curr; } return -1; } int main(){ int n; cin >> n; // your code goes here vector> res(n - 1, vector(n - 1)); for (int i = 0; i < n - 1; i++) { for (int j = i; j < n - 1; j++) { int step = getSteps(n, i + 1, j + 1); res[i][j] = step; res[j][i] = step; } } for (int i = 0; i < n - 1; i++) { for (int j = 0; j < n - 1; j++) { cout << res[i][j] << " "; } cout << endl; } return 0; }