#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; bool isvalid(int x, int y, int n, map, bool>& visited) { if (x >= 1 && x <=n && y >= 1 && y <= n && !visited.count(make_pair(x, y))) return true; return false; } int solve(int x1, int y1, int x2, int y2, int a, int b, int n) { queue, int> > que; map, bool> visited; que.push(make_pair(make_pair(x1, y1), 0)); visited[make_pair(x1, y1)] = true; while(!que.empty()) { pair, int> temp = que.front(); que.pop(); //cout << temp.first.first << " " << temp.first.second << endl; if (temp.first.first == x2 && temp.first.second == y2) { //cout << "Found the destination in " << temp.second << "steps" << endl; return temp.second; } //cout << " I am here " << endl; if (isvalid(temp.first.first + a, temp.first.second + b, n, visited)) { //cout << temp.first.first + a << " , " << temp.first.second + b << "are valid" << endl; que.push(make_pair(make_pair(temp.first.first+a, temp.first.second+b), temp.second +1)); visited[make_pair(temp.first.first+a, temp.first.second+b)] = true; } if (isvalid(temp.first.first + a, temp.first.second - b, n, visited)) { //cout << temp.first.first + a << " , " << temp.first.second - b << "are valid" << endl; que.push(make_pair(make_pair(temp.first.first+a, temp.first.second-b), temp.second +1)); visited[make_pair(temp.first.first+a, temp.first.second-b)] = true; } if (isvalid(temp.first.first - a, temp.first.second + b, n, visited)) { //cout << temp.first.first - a << " , " << temp.first.second + b << "are valid" << endl; que.push(make_pair(make_pair(temp.first.first-a, temp.first.second+b), temp.second +1)); visited[make_pair(temp.first.first-a, temp.first.second+b)] = true; } if (isvalid(temp.first.first - a, temp.first.second - b, n, visited)) { //cout << temp.first.first - a << " , " << temp.first.second - b << "are valid" << endl; que.push(make_pair(make_pair(temp.first.first-a, temp.first.second-b), temp.second +1)); visited[make_pair(temp.first.first-a, temp.first.second-b)] = true; } if (isvalid(temp.first.first + b, temp.first.second + a, n, visited)) { //cout << temp.first.first + b << " , " << temp.first.second + a << "are valid" << endl; que.push(make_pair(make_pair(temp.first.first+b, temp.first.second+a), temp.second +1)); visited[make_pair(temp.first.first+b, temp.first.second+a)] = true; } if (isvalid(temp.first.first + b, temp.first.second -a, n, visited)) { //cout << temp.first.first + b << " , " << temp.first.second - a << "are valid" << endl; que.push(make_pair(make_pair(temp.first.first+b, temp.first.second-a), temp.second +1)); visited[make_pair(temp.first.first+b, temp.first.second-a)] = true; } if (isvalid(temp.first.first -b, temp.first.second + a, n, visited)) { //cout << temp.first.first -b << " , " << temp.first.second +a << "are valid" << endl; que.push(make_pair(make_pair(temp.first.first-b, temp.first.second+a), temp.second +1)); visited[make_pair(temp.first.first-b, temp.first.second+a)] = true; } if (isvalid(temp.first.first -b, temp.first.second -a, n, visited)) { //cout << temp.first.first -b << " , " << temp.first.second - a << "are valid" << endl; que.push(make_pair(make_pair(temp.first.first-b, temp.first.second-a), temp.second +1)); visited[make_pair(temp.first.first-b, temp.first.second-a)] = true; } } return -1; } int main(){ int n; cin >> n; vector > vec(n-1, vector (n-1,-1)); // your code goes here for (int i =1 ; i <= n-1; ++i){ for (int j = 1; j <= n-1; ++j) { vec[i-1][j-1] = solve(1, 1, n, n, i, j, n); } } for (int i = 0; i < n-1; ++i) { for (int j = 0; j < n-1; ++j) cout << vec[i][j] << " "; cout << endl; } return 0; }