#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; /* I just figured it out. I did a variant of a breadth first search. Try building a board where each element is the minimum amount of moves it takes the peice to move there. Then, you can look at the (n-1, n-1) element of the board and it should contain the number of moves required. Or it will be 0 if it can't be reached. I didn't run into any timeout problems! */ int findMinMoves(int n, int a, int b) { vector> isVisited(n, vector(n, false)); //vector> minMovesNeeded(n, vector(n, 0)); vector> pD; // possible directions pD.push_back({a, b}); pD.push_back({b, a}); pD.push_back({-b, a}); pD.push_back({a, -b}); pD.push_back({b, -a}); pD.push_back({-a, b}); pD.push_back({-a, -b}); pD.push_back({-b, -a}); queue> queue; isVisited[0][0] = true; queue.push({0,0,0}); while (!queue.empty()) { int x = queue.front()[0]; int y = queue.front()[1]; int count = queue.front()[2]; queue.pop(); //cout << "(" << x << "," << y << ")" << endl; if (x == n - 1 && y == n - 1) return count; for (int i = 0; i < 8; i++) { int nextX = x + pD[i][0]; int nextY = y + pD[i][1]; bool isOnTheBoard = (nextX >= 0) && (nextX < n) && (nextY >= 0) && (nextY < n); if (isOnTheBoard && !isVisited[nextX][nextY]) { isVisited[nextX][nextY] = true; queue.push({nextX, nextY, count + 1}); } } } if (!isVisited[n - 1][n - 1]) return -1; else return 0; //return count; //return 0; } int main(){ int n; cin >> n; vector> result; result.resize(n-1); for (int i = 0; i < result.size(); i++) { result[i].resize(n - 1); } for (int i = 0; i < result.size(); i++) { for (int j = 0; j < result[i].size(); j++) { //cout << "BEHAVIOR:" << i+1 << " " << j+1 << endl; if (result[j][i] > 0) { //cout << "skip" << endl; result[i][j] = result[j][i]; } else { //cout << "process" << endl; result[i][j] = findMinMoves(n, i + 1, j + 1); } //cout << "\nEND\n\n" << endl; } } for (int i = 0; i < result.size(); i++) { for (int j = 0; j < result[i].size(); j++) { cout << result[i][j] << " "; } cout << endl; } return 0; }