#P1713. 麦当劳叔叔的难题
麦当劳叔叔的难题
题目描述
话说我们铭铭小朋友成功的回答了爸爸的问题,自然少不了要去索要些奖励,抠门的爸爸一看报纸,嘿,门口的麦当劳在搞活动,还有免费午餐哦,不过前提条件:得正确回答麦当劳叔叔的问题。
问题是这样描述的:
“我面前有很多个小朋友,我希望你帮我找到一个最聪明的小朋友。我心目中最聪明的就是第一个跑进麦当劳大门的,我希望你帮我找出最聪明和最不聪明的小朋友,可能的最大的到达时间差。但是,小朋友只能按照一个特殊的规则前进。小朋友面前有一个 的格子矩阵,左下角的格子是起点,右上角的格子是大门。每个孩子每秒可以走向 上、下、左、右 前进一个格子,每个格子只能经过一次。但矩阵中间有一些障碍区,不能通过,只能绕过。”
例如, 的矩阵,格子 为障碍区,黑格子就是一条可行的路线。时间为 。
输入格式
第一行为两个整数 。
第二至第 行里,每行描述一个障碍区。用两个整数表示 。
输出格式
仅一行,那个最大的时间差。
4 3
1 1
2 3
4 2
4
提示
,,。