#include #include #include #include #include #include #include using namespace std; struct Node { Node(int num_moves, int pos_x, int pos_y) { moves = num_moves; x = pos_x; y = pos_y; } //int dist; int moves; int x; int y; }; /* int GetDistanceToGoal(int x, int y, int n) { return n - x + n - y; } */ int GetNodeHash(int x, int y) { return x * 100 + y; } void GetChildren(Node node, std::vector& children, int a, int b, int n) { int posX = node.x + a; int posY = node.y - b; if(posX < n && posY >= 0) { children.emplace_back(node.moves + 1, posX, posY); } posX = node.x + b; posY = node.y - a; if(posX < n && posY >= 0) { children.emplace_back(node.moves + 1, posX, posY); } //posX = node.x + b; posY = node.y + a; if(posX < n && posY < n) { children.emplace_back(node.moves + 1, posX, posY); } posX = node.x + a; posY = node.y + b; if(posX < n && posY < n) { children.emplace_back(node.moves + 1, posX, posY); } posX = node.x - a; //posY = node.y + b; if(posX >= 0 && posY < n) { children.emplace_back(node.moves + 1, posX, posY); } posX = node.x - b; posY = node.y + a; if(posX >= 0 && posY < n) { children.emplace_back(node.moves + 1, posX, posY); } //posX = node.x - b; posY = node.y - a; if(posX >= 0 && posY >= 0) { children.emplace_back(node.moves + 1, posX, posY); } posX = node.x - a; posY = node.y - b; if(posX >= 0 && posY >= 0) { children.emplace_back(node.moves + 1, posX, posY); } } int main() { int n; cin >> n; int goalHash = GetNodeHash(n - 1, n - 1); for(int a = 1; a < n; ++a) { for(int b = 1; b < n; ++b) { std::unordered_set visitedNodes; std::queue q; q.emplace(0, 0, 0); bool foundGoal = false; while(!foundGoal && !q.empty()) { Node node = q.front(); q.pop(); //check that we haven't already visited this node int hash = GetNodeHash(node.x, node.y); if(visitedNodes.find(hash) != visitedNodes.end()) { continue; } else { visitedNodes.insert(hash); } //check that node isn't the goal if(hash == goalHash) { foundGoal = true; std::cout << node.moves << " "; } //add children onto queue std::vector children; GetChildren(node, children, a, b, n); for(auto& child : children) { q.push(child); } } if(!foundGoal) { std::cout << "-1 "; } } std::cout << std::endl; } return 0; }