#include #include #include using namespace std; typedef pair ii; typedef vector vi; typedef vector vvi; typedef vector vvvi; typedef vector vvvvi; typedef vector vii; typedef vector vvii; typedef vector vvvii; #define x first #define y second int h, w; vvi plots; vvvii neighs; // def find_paths(dest_x, dest_y, dest): // seen, stack = [[0] * w for _ in range(h)], [(dest_x, dest_y, 0)] // while stack: // x, y, dist = stack.pop() // for xx, yy in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)): // if 0 <= xx < w and 0 <= yy < h and neighs[dest - 1][yy][xx] == (x, y) and not seen[yy][xx]: // stack.append((xx, yy, dist + 1)) // seen[yy][xx] = dist + 1 // return seen void find_paths(vvi &seen, int dest_x, int dest_y, int dest) { vii stack_points = {{dest_x, dest_y}}; vi stack_dist = {0}; while (stack_points.size()) { ii curr = stack_points.back(); int x = curr.x, y = curr.y; stack_points.pop_back(); int dist = stack_dist.back(); stack_dist.pop_back(); for (ii p : vii{ii{x - 1, y}, ii{x + 1, y}, ii{x, y - 1}, ii{x, y + 1}}) { if (0 <= p.x && p.x < w && 0 <= p.y && p.y < h) { if (neighs[dest][p.y][p.x] == ii{x, y}) { if (!seen[p.y][p.x]) { stack_points.push_back(p); stack_dist.push_back(dist + 1); seen[p.y][p.x] = dist + 1; }}} } } } int main() { cin >> h >> w; plots = vvi(h, vi(w, 0)); for (int y = 0; y < h; y++) { for (int x = 0; x < w; x++) { cin >> plots[y][x]; } } // neighs = [[[min((abs(neigh - dest), abs(neigh - plots[y][x]), xx, yy) for xx, yy, neigh in // ((xx, yy, plots[yy][xx]) for xx, yy in ((x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)) // if 0 <= xx < w and 0 <= yy < h))[2:] // for x in range(w)] for y in range(h)] for dest in range(1, w * h + 1)] neighs = vvvii(w * h + 1, vvii(h, vii(w, ii{0, 0}))); for (int dest = 1; dest <= w * h; ++dest) { for (int y = 0; y < h; ++y) { for (int x = 0; x < w; ++x) { ii best_neigh, best_val = {(int) 1e9, (int) 1e9}; for (ii p : vii{ii{x - 1, y}, ii{x + 1, y}, ii{x, y - 1}, ii{x, y + 1}}) { if (0 <= p.x && p.x < w && 0 <= p.y && p.y < h) { int neigh = plots[p.y][p.x]; ii val = ii{abs(neigh - dest), abs(neigh - plots[y][x])}; if (val.x < best_val.x || val.x == best_val.x && val.y < best_val.y) { best_neigh = ii{p.x, p.y}; best_val = val; } } } neighs[dest][y][x] = best_neigh; } } } // paths = [[find_paths(x, y, plots[y][x]) for x in range(w)] for y in range(h)] vvvvi paths = vvvvi(h, vvvi(w, vvi(h, vi(w, 0)))); for (int y = 0; y < h; ++y) { for (int x = 0; x < w; ++x) { find_paths(paths[y][x], x, y, plots[y][x]); } } // best = min((max(paths[dest_y][dest_x][kiosk_y][kiosk_x] or 1e9 for dest_y in range(h) for dest_x in range(w)), // plots[kiosk_y][kiosk_x]) for kiosk_y in range(h) for kiosk_x in range(w)) int best_dist = (int) 1e9, best_kiosk = -1; for (int kiosk_y = 0; kiosk_y < h; ++kiosk_y) { for (int kiosk_x = 0; kiosk_x < w; ++kiosk_x) { int max_dist = 0; for (int dest_y = 0; dest_y < h; ++dest_y) { for (int dest_x = 0; dest_x < w; ++dest_x) { int dist = paths[dest_y][dest_x][kiosk_y][kiosk_x]; if (dist == 0) dist = (int) 1e9; max_dist = max(dist, max_dist); } } if (max_dist < best_dist) { best_dist = max_dist; best_kiosk = plots[kiosk_y][kiosk_x]; } } } // print("impossible") if best[0] == 1e9 else print(*best[::-1]) if (best_kiosk == -1) { cout << "impossible" << endl; } else { cout << best_kiosk << " " << best_dist << endl; } }