請詳見註解~

from collections import deque
n = int(input()) # n * n 矩陣邊長
square = [list(map(int, input().split())) for _ in range(n)] # 讀 n 行 每行有 n 個元素
directions = [(-1, 0), (1, 0), (0, -1), (0, 1)] # 四個允許的道路鋪設方向

def check_pass(max_diff: int) -> bool: # 回傳這個最大距離差 可否通行
    '''用 BFS 廣度搜索 檢查是否存在一條最大高度差 <= max_diff 的路徑'''
    queue = deque([(0, 0)]) # (座標x, 座標y) 以 (0, 0) 為起點開始搜索到終點
    visited = [[False] * n for _ in range(n)] # 紀錄每個點是否被走訪過
    visited[0][0] = True # 那第一個點在 queue 了 就先打上標記
    
    while queue:
        x, y = queue.popleft()
        if x == n - 1 and y == n - 1: return True # 成功走到終點
        for dx, dy in directions: # 差看所有鋪設方向 (廣度搜索) 把所有可行的下一步找出來
            new_x, new_y = x + dx, y + dy # 新的座標
            if 0 <= new_x < n and 0 <= new_y < n and not visited[new_x][new_y]:
                if abs(square[new_x][new_y] - square[x][y]) <= max_diff: # 距離差要小於或等於 max_diff
                    queue.append([new_x, new_y])
                    visited[new_x][new_y] = True

    return False

def shortest_path(max_diff: int) -> int: # 回傳這個最大距離差 的步數
    '''一樣用 BFS 廣度搜索'''
    queue = deque([(0, 0, 0)])  # (x, y, 步數)
    visited = [[False] * n for _ in range(n)] # 紀錄每個點是否被走訪過
    visited[0][0] = True # 那第一個點在 queue 了 就先打上標記
    
    while queue:
        x, y, steps = queue.popleft()
        if x == n - 1 and y == n - 1: return steps # 成功找到最短方法 回傳使用步數
        for dx, dy in directions: # 差看所有鋪設方向 (廣度搜索) 一樣把所有可行的下一步找出來
            next_x, next_y = x + dx, y + dy # 下一步的座標
            if 0 <= next_x < n and 0 <= next_y < n and not visited[next_x][next_y]:
                if abs(square[next_x][next_y] - square[x][y]) <= max_diff: # 距離差要小於或等於 max_diff
                    queue.append([next_x, next_y, steps + 1])
                    visited[next_x][next_y] = True

    return -1 # 理論上不會執行到這行

if __name__ == '__main__':
    # 用二分搜找<最小的> 最大高度差（max_diff）
    l, r = 0, max(max(row) for row in square) - min(min(row) for row in square) # r 是預設是最大的最大高度差
    while l < r:
        mid = (l + r) // 2
        if check_pass(mid): r = mid # 嘗試更小的最大高度差 (目的是找到最小)
        else: l = mid + 1 # 最大高度差太小了 必須嘗試更大的 max_diff

    # 找到最小的 max_diff 後，計算最短路徑長度
    min_max_diff = l
    min_path_length = shortest_path(min_max_diff)

    # 輸出結果
    print(min_max_diff)
    print(min_path_length)