#include #include #include #include #include class SymMatrix { public: explicit SymMatrix(int N) { m_v.resize(N); for (auto& row : m_v) row.resize(N, -1); } void set(int row, int col, int value) { m_v[row][col] = value; if (row != col) m_v[col][row] = value; } int get(int row, int col) const { return m_v[row][col]; } private: std::vector> m_v; }; struct Index { int row; int col; bool isValid(int n) const { return row < n && col < n && row > -1 && col > -1; } bool operator==(const Index& other) const { return row == other.row && col == other.col; } }; class Map { public: Map() = default; void insert(const Index& index) { m_map[index.row].insert(index.col); } bool contains(const Index& index) { auto it = m_map.find(index.row); if (it == m_map.end()) return false; auto it2 = it->second.find(index.col); if (it2 == it->second.end()) return false; return true; } private: std::unordered_map> m_map; }; std::vector generatePossibleIndexes(int a, int b, Index from) { std::vector ret; ret.reserve(a != b ? 8 : 4); ret.push_back({ from.row + a, from.col + b }); ret.push_back({ from.row + a, from.col - b }); ret.push_back({ from.row - a, from.col + b }); ret.push_back({ from.row - a, from.col - b }); if (a != b) { ret.push_back({ from.row + b, from.col + a }); ret.push_back({ from.row + b, from.col - a }); ret.push_back({ from.row - b, from.col + a }); ret.push_back({ from.row - b, from.col - a }); } return ret; } int findPathLength(int a, int b, int n, Index currentPosition, Map& map) { if (currentPosition.row == n - 1 && currentPosition.col == n - 1) return 0; auto possibleNextPosition = generatePossibleIndexes(a, b, currentPosition); auto map_internal = map; auto minLength = std::numeric_limits::max(); for (auto& position : possibleNextPosition) { if (!position.isValid(n) || map.contains(position)) continue; map_internal.insert(position); auto nextLength = findPathLength(a, b, n, position, map_internal); if (nextLength != -1) minLength = std::min(minLength, nextLength + 1); } if (minLength == std::numeric_limits::max()) return -1; return minLength; } int main() { auto n = 0; std::cin >> n; SymMatrix result(n - 1); for (auto a = 0; a < n - 1; ++a) for (auto b = a; b < n - 1; ++b) { if (a == b) { if (a == n - 2) result.set(a, b, 1); else result.set(a, b, n - 1); } Map map; result.set(a, b, findPathLength(a + 1, b + 1, n, { 0, 0 }, map)); } for (auto a = 0; a < n - 1; ++a) { for (auto b = 0; b < n - 1; ++b) std::cout << result.get(a, b) << " "; std::cout << std::endl; } return 0; }