#include using std::intptr_t, std::size_t, std::uint64_t; struct coords { intptr_t x; intptr_t y; }; coords operator+(const coords &a, const coords &b) { return coords{a.x + b.x, a.y + b.y}; } bool operator==(const coords &a, const coords &b) { return a.x == b.x && a.y == b.y; } template struct table { size_t width; size_t height; std::vector elements; typedef typename decltype(elements)::reference reference; table(size_t width, size_t height) : width(width), height(height), elements(width * height) {} reference operator[](coords c) { return elements[c.y * width + c.x]; } bool is_in_bounds(coords c) { return 0 <= c.x && c.x < width && 0 <= c.y && c.y < height; } }; std::array directions = {coords{0, 1}, coords{1, 0}, coords{0, -1}, coords{-1, 0}}; table> maximum_distances(table &heights, coords origin) { table> distances(heights.width, heights.height); table calculated(heights.width, heights.height); std::queue queue; auto is_lower_neighbour = [&heights](coords cell, coords neighbour) { return heights.is_in_bounds(neighbour) && heights[neighbour] < heights[cell]; }; for (intptr_t x = 0; x < heights.width; x++) { for (intptr_t y = 0; y < heights.width; y++) { coords cell = {x, y}; bool ready = true; for (coords dir : directions) { if (is_lower_neighbour(cell, cell + dir)) { ready = false; } } if (ready) queue.push(cell); } } while (!queue.empty()) { coords cell = queue.front(); queue.pop(); if (calculated[cell]) continue; if (cell == origin) distances[cell] = 0; for (coords dir : directions) { coords neighbour = cell + dir; if (!is_lower_neighbour(cell, neighbour)) continue; if (!distances[neighbour]) continue; distances[cell] = std::max(distances[cell], {*distances[neighbour] + 1}); } calculated[cell] = true; for (coords dir : directions) { coords neighbour = cell + dir; if (!heights.is_in_bounds(neighbour)) continue; if (calculated[neighbour]) continue; bool ready = true; for (coords dir : directions) { if (!is_lower_neighbour(neighbour, neighbour + dir)) continue; if (!calculated[neighbour + dir]) ready = false; } if (ready) queue.push(neighbour); } } return distances; } std::vector retrace_path(table &heights, table> &dists, coords point) { std::vector path; while (*dists[point] != 0) { for (coords direction : directions) { coords neighbour = point + direction; if (!dists.is_in_bounds(neighbour)) continue; if (heights[neighbour] >= heights[point]) continue; if (dists[neighbour] && *dists[neighbour] == *dists[point] - 1) { point = neighbour; break; } } path.push_back(point); } return path; } std::vector longest_trip(table heights, coords start, coords end) { table> dists_from_start = maximum_distances(heights, start); table> dists_from_end = maximum_distances(heights, end); auto score_peak = [&heights, &dists_from_start, &dists_from_end](coords c) { std::optional total_length; if (dists_from_start[c] && dists_from_end[c]) total_length = *dists_from_start[c] + *dists_from_end[c]; return std::make_pair(total_length, heights[c]); }; coords peak = {0, 0}; for (ptrdiff_t x = 0; x < heights.width; x++) { for (ptrdiff_t y = 0; y < heights.height; y++) { if (score_peak({x, y}) > score_peak(peak)) { peak = {x, y}; } } } std::vector to_start = retrace_path(heights, dists_from_start, peak); std::vector to_end = retrace_path(heights, dists_from_end, peak); std::vector result; result.insert(result.end(), to_start.rbegin(), to_start.rend()); result.push_back(peak); result.insert(result.end(), to_end.begin(), to_end.end()); return result; } int main() { size_t height, width; std::cin >> height >> width; ptrdiff_t start_x, start_y, end_x, end_y; std::cin >> start_x >> start_y >> end_x >> end_y; coords start{start_x, start_y}; coords end{end_x, end_y}; table heights(width, height); for (ptrdiff_t y = 0; y < height; y++) for (ptrdiff_t x = 0; x < width; x++) std::cin >> heights[{x, y}]; std::vector path = longest_trip(heights, start, end); std::cout << path.size() << '\n'; for (coords c : path) std::cout << c.x << ' ' << c.y << '\n'; }