#include #include #include #include #include #include using namespace std; struct Block { int goal_mark; int steps : 30; bool visited_goal : 1; bool visited_start : 1; }; struct AddrPair { unsigned int x; unsigned int y; }; int main() { int n; cin >> n; vector grid(n * n, {0, -1, false, false}); deque start_q; auto&& clear_grid = [&grid, n]() { for(auto& b : grid) { b.goal_mark = 0; b.visited_goal = false; b.visited_start = false; } }; auto&& set_steps = [&grid, n](unsigned int x, unsigned int y, int val) -> void { grid[y * n + x].steps = val; }; auto&& get_at = [&grid, n](unsigned int x, unsigned int y) -> Block& { return grid[y * n + x]; }; auto&& is_on_grid = [n](int x, int y) -> bool { if (x < 0 || y < 0 || x >= n || y >= n) return false; return true; }; auto&& mark_goal_seen = [&grid, n] (unsigned int x, unsigned int y ) -> void { grid[y * n + x].visited_goal = true; }; auto&& mark_start_seen = [&grid, n] (unsigned int x, unsigned int y ) -> void { grid[y * n + x].visited_start = true; }; set_steps(n - 2, n - 2, 1); // The only one move case // Do an interative BFS from start and goal for each pair. // Taking advantage of mirroring the moves for (unsigned int i = 1; i < n - 1; ++i) { if ( (n - 1) % i == 0) set_steps(i - 1, i - 1, (n - 1) / i); for (unsigned int j = i + 1; j < n; ++j) { unsigned int round = 0; start_q.clear(); clear_grid(); auto&& iteration = [&](AddrPair sp) -> int { mark_start_seen(sp.x, sp.y); mark_goal_seen(n - 1 - sp.x, n - 1 - sp.y); get_at(n -1 - sp.x, n - 1 - sp.y).goal_mark = round; // test for finding of min moves if (get_at(sp.x, sp.y).visited_goal) { return round + get_at(sp.x, sp.y).goal_mark; } // queue nodes to explore next iteration if (is_on_grid(sp.x + i, sp.y + j) && !get_at(sp.x + i, sp.y + j).visited_start) { start_q.emplace_back(AddrPair{sp.x + i, sp.y + j}); } if (is_on_grid(sp.x + i, sp.y - j) && !get_at(sp.x + i, sp.y - j).visited_start) { start_q.emplace_back(AddrPair{sp.x + i, sp.y - j}); } if (is_on_grid(sp.x - i, sp.y + j) && !get_at(sp.x - i, sp.y + j).visited_start) { start_q.emplace_back(AddrPair{sp.x - i, sp.y + j}); } if (is_on_grid(sp.x - i, sp.y - j) && !get_at(sp.x - i, sp.y - j).visited_start) { start_q.emplace_back(AddrPair{sp.x - i, sp.y - j}); } if (is_on_grid(sp.x + j, sp.y + i) && !get_at(sp.x + j, sp.y + i).visited_start) { start_q.emplace_back(AddrPair{sp.x + j, sp.y + i}); } if (is_on_grid(sp.x + j, sp.y - i) && !get_at(sp.x + j, sp.y - i).visited_start) { start_q.emplace_back(AddrPair{sp.x + j, sp.y - i}); } if (is_on_grid(sp.x - j, sp.y + i) && !get_at(sp.x - j, sp.y + i).visited_start) { start_q.emplace_back(AddrPair{sp.x - j, sp.y + i}); } if (is_on_grid(sp.x - j, sp.y - i) && !get_at(sp.x - j, sp.y - i).visited_start) { start_q.emplace_back(AddrPair{sp.x - j, sp.y - i}); } return 0; }; start_q.emplace_back(AddrPair{0, 0}); while(!start_q.empty()) { for (size_t num = start_q.size(); num > 0; --num) { AddrPair a = start_q.front(); start_q.pop_front(); int res = iteration(a); if (res) { set_steps(i - 1, j - 1, res); set_steps(j - 1, i - 1, res); start_q.clear(); break; } } ++round; } } } for (size_t i = 0; i < n - 1; ++i) { for (size_t j = 0; j < n - 1; ++j) { cout << get_at(j, i).steps << ' '; } cout << '\n'; } /* Enter your code here. Read input from STDIN. Print output to STDOUT */ return 0; }