2146: 接待亭
内存限制：512 MB
时间限制：2 S
标准输入输出
题目类型：传统
评测方式：Special Judge
上传者：
提交：2
通过：2
题目描述
你计划开办一个布置精美宁静的露营地。
你已经购买了一片土地，并将其分割成一个 h × w 的网格，用编号 a[i][j] 从 1 到 h·w 标记每个网格。
然而，你忘记了一件事：你还需要在其中一个网格上放置接待亭。
你希望最大限度地减少客人从接待亭到他们的网格所需行走的距离。
但是客人不会选择最短路径前往他们的网格，而是按照以下步骤进行操作，从接待亭开始：
• 查看四个相邻网格的编号。
• 前往编号最接近目标编号的网格。如果有多个网格相同，则选择与当前网格编号最接近的网格。
• 重复以上步骤直到到达目标地块。
注意，该过程在某些情况下可能无法终止。
给定网格的编号，找到接待亭最佳位置的网格编号以及从该亭子到任何网格的最大步行距离。
如果对于每个可能的接待亭位置，存在至少一个网格无法达到，则输出"impossible"。
你已经购买了一片土地，并将其分割成一个 h × w 的网格，用编号 a[i][j] 从 1 到 h·w 标记每个网格。
然而，你忘记了一件事：你还需要在其中一个网格上放置接待亭。
你希望最大限度地减少客人从接待亭到他们的网格所需行走的距离。
但是客人不会选择最短路径前往他们的网格，而是按照以下步骤进行操作，从接待亭开始：
• 查看四个相邻网格的编号。
• 前往编号最接近目标编号的网格。如果有多个网格相同，则选择与当前网格编号最接近的网格。
• 重复以上步骤直到到达目标地块。
注意，该过程在某些情况下可能无法终止。
给定网格的编号，找到接待亭最佳位置的网格编号以及从该亭子到任何网格的最大步行距离。
如果对于每个可能的接待亭位置，存在至少一个网格无法达到，则输出"impossible"。
输入格式
第一行为正整数 h 和 w，2≤h,w≤40。
接下来 h 行，每行 w 个整数，表示网格编号，1≤a[i][j]≤hw。
接下来 h 行，每行 w 个整数，表示网格编号，1≤a[i][j]≤hw。
输出格式
如果存在一个接待亭的位置，使得可以到达其他每个地块，则输出接待亭的最佳位置和相应的最大步行距离。
否则，输出“impossible”。
如果有多个有效解决方案，可以输出其中任意一个。
否则，输出“impossible”。
如果有多个有效解决方案，可以输出其中任意一个。
输入样例 复制
样例1：
2 3
1 2 3
6 5 4
样例2：
3 3
1 4 8
7 5 2
3 9 6
样例3：
3 3
9 3 1
4 7 2
8 6 5
输出样例 复制
样例1：
2 2
样例2：
impossible
样例3：
4 3数据范围与提示
上图为样例3的一组合法解，接待亭在编号为4的网格位置是最优的，最远距离为3。
来源：2022.BAPC