#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 xy{ int x; int y; int no_moves; }; bool inlimits(int p, int n){ return ((p >= 0) && (p < n)); } void add_next(vector>& visited, queue& to_visit, xy loc, int a, int b, int n){ for (int i = -1; i <= 1; i+=2){ for (int j = -1; j <= 1; j+=2){ if (inlimits(loc.x + i * a, n) && (inlimits(loc.y + j * b, n))){ int new_x = loc.x + i * a; int new_y = loc.y + j * b; if (!visited[new_x][new_y]){ visited[new_x][new_y] = true; xy new_loc = {new_x, new_y, loc.no_moves + 1}; to_visit.push(new_loc); } } if (inlimits(loc.x + i * b, n) && (inlimits(loc.y + j * a, n))){ int new_x = loc.x + i * b; int new_y = loc.y + j * a; if (!visited[new_x][new_y]){ visited[new_x][new_y] = true; xy new_loc = {new_x, new_y, loc.no_moves + 1}; to_visit.push(new_loc); } } } } } int count_moves(int n, int a, int b){ vector> visited(n, vector(n, false)); xy loc = {0,0,0}; queue to_visit; to_visit.push(loc); visited[0][0] = true; while (!to_visit.empty()){ loc = to_visit.front(); to_visit.pop(); if ((loc.x == n-1) && (loc.y == n-1)) return loc.no_moves; add_next(visited, to_visit, loc, a, b, n); } return -1; } void print_results(int n, vector>& results){ for (int a = 1; a < n; a++){ for (int b = 1 ; b < n; b++){ cout << results[a][b] << " "; } cout << endl; } } int main(){ int n; cin >> n; // your code goes here vector> results(n, vector(n, 0)); for (int a = 1; a < n ; a++) for (int b = a; b < n; b++){ results[a][b] = count_moves(n, a, b); results[b][a] = results[a][b]; } print_results(n, results); return 0; }