#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; int main() { int n; cin >> n; // your code goes here int a, b; int x1, y1, x2, y2; int **mat; bool **vis; mat = new int*[n-1]; for(a = 0;a < n-1;a++) mat[a] = new int[n-1]; vis = new bool*[n]; for(a = 0;a < n;a++) vis[a] = new bool[n]; for(a = 0;a < n-1;a++) for(b = 0;b < n-1;b++) { mat[a][b] = -1; } for(a = 0;a < n;a++) for(b = 0;b < n;b++) vis[a][b] = false; x1 = 1; y1 = 1; a = 1; b = 1; x2 = 1; y2 = 1; int moves = 0; queue, int>> q; pair, int> p; int x = 0; while (a < n && b < n) { x = 0; q.push(make_pair(make_pair(x1, y1), moves)); for(int i = 0;i < n;i++) { for(int j = 0;j < n;j++) vis[i][j] = false; } while(!q.empty()) { p = q.front(); q.pop(); x1 = p.first.first; y1 = p.first.second; moves = p.second; moves++; x2 = x1 - a; y2 = y1 - b; if (x2 == n && y2 == n) { mat[a-1][b-1] = moves; break; } else if (x2 > 0 && y2 > 0 && !vis[x2-1][y2-1]) { q.push(make_pair(make_pair(x2, y2), moves)); vis[x2-1][y2-1] = true; } x2 = x1 + a; y2 = y1 - b; if (x2 == n && y2 == n) { mat[a-1][b-1] = moves; break; } else if (x2 <= n && y2 > 0 && !vis[x2-1][y2-1]) { q.push(make_pair(make_pair(x2, y2), moves)); vis[x2-1][y2-1] = true; } x2 = x1 - a; y2 = y1 + b; if (x2 == n && y2 == n) { mat[a-1][b-1] = moves; break; } else if (x2 > 0 && y2 <= n && !vis[x2-1][y2-1]) { q.push(make_pair(make_pair(x2, y2), moves)); vis[x2-1][y2-1] = true; } x2 = x1 + a; y2 = y1 + b; if (x2 == n && y2 == n) { mat[a-1][b-1] = moves; break; } else if (x2 <= n && y2 <= n && !vis[x2-1][y2-1]) { q.push(make_pair(make_pair(x2, y2), moves)); vis[x2-1][y2-1] = true; } x2 = x1 - b; y2 = y1 - a; if (x2 == n && y2 == n) { mat[a-1][b-1] = moves; break; } else if (x2 > 0 && y2 > 0 && !vis[x2-1][y2-1]) { q.push(make_pair(make_pair(x2, y2), moves)); vis[x2-1][y2-1] = true; } x2 = x1 + b; y2 = y1 - a; if (x2 == n && y2 == n) { mat[a-1][b-1] = moves; break; } else if (x2 <= n && y2 > 0 && !vis[x2-1][y2-1]) { q.push(make_pair(make_pair(x2, y2), moves)); vis[x2-1][y2-1] = true; } x2 = x1 - b; y2 = y1 + a; if (x2 == n && y2 == n) { mat[a-1][b-1] = moves; break; } else if (x2 > 0 && y2 <= n && !vis[x2-1][y2-1]) { q.push(make_pair(make_pair(x2, y2), moves)); vis[x2-1][y2-1] = true; } x2 = x1 + b; y2 = y1 + a; if (x2 == n && y2 == n) { mat[a-1][b-1] = moves; break; } else if (x2 <= n && y2 <= n && !vis[x2-1][y2-1]) { q.push(make_pair(make_pair(x2, y2), moves)); vis[x2-1][y2-1] = true; } } q = queue, int>>(); b++; if (b == n) { a++; b = 1; } x1 = 1; y1 = 1; moves = 0; } for(a = 0;a < n-1;a++) { for(b = 0;b < n-1;b++) cout<