knight_moves_grid_3217.cpp (815B)
1 #include <iostream> 2 #include <queue> 3 #include <tuple> 4 #include <vector> 5 6 struct Node { 7 int i; 8 int j; 9 int d; 10 }; 11 12 int main() { 13 int n; 14 std::cin >> n; 15 std::vector<std::vector<int>> a(n, std::vector<int>(n, 1e7)); 16 std::queue<Node> q; 17 18 q.push(Node{0, 0, 0}); 19 while (!q.empty()) { 20 auto v = q.front(); 21 q.pop(); 22 if (v.i < 0 || v.j < 0 || v.i >= n || v.j >= n || a[v.i][v.j] <= v.d) 23 continue; 24 a[v.i][v.j] = v.d; 25 q.push(Node{v.i-2, v.j-1, v.d+1}); 26 q.push(Node{v.i-2, v.j+1, v.d+1}); 27 q.push(Node{v.i-1, v.j-2, v.d+1}); 28 q.push(Node{v.i-1, v.j+2, v.d+1}); 29 q.push(Node{v.i+2, v.j-1, v.d+1}); 30 q.push(Node{v.i+2, v.j+1, v.d+1}); 31 q.push(Node{v.i+1, v.j-2, v.d+1}); 32 q.push(Node{v.i+1, v.j+2, v.d+1}); 33 } 34 35 for (auto& v : a) { 36 for (auto& x : v) 37 std::cout << x << " "; 38 std::cout << "\n"; 39 } 40 }