• [1729] 小明想要再去次成都

  • 时间限制: 1000 ms　内存限制: 65535 K
  • 问题描述

  • 在一个n行m列的地图上，有n x m个点，每个点代表着一个城市，第i行j列的位置坐标为（i，j）。因为每个城市对于飞机的飞行高度都有一定的限制，所以并不是所有城市都能飞行的。飞机一开始在（1,1）的城市上空，且高度为h【i，j】，由于空管对其管控，每次要求只能上下左右四个方向飞行。并且每次飞机从一个城市飞往另一个城市的最大可抬升高度为L，也就意味着只有两个城市的限制飞行高度差必须小于等于飞机的最大可抬升高度L，飞机才可以前往。飞机是否能飞往成都，帮助小明实现愿望呢？你需要帮助他解答这个问题。你只需输出飞机飞行到成都（n，m）抬升的次数。若无法到达输出-1。

  • 输入
  • 第一行给出一个整数T(1<=T<=100),表示测试数据的数目。
    对于每组测试数据，
    第一行是三个正整数n，m，L（1<=n,m<=100，0<=L<=100000），分别表示地图的行数，列数和飞机最大可抬升高度，
    接下来n行，每行m个城市，表示地图每个城市飞机限行的最低高度h【i，j】。（0<=h【i，j】<=100000）
  • 输出
  • 对于每一组数据，输出一个整数，表示飞行到成都（n，m）飞机需要抬升的最少次数。
  • 样例输入
  • 2
2 3 10
10 30 10
0 5 5
3 5 1
1 6 7 12 13
2 5 8 11 14
3 4 9 10 15
  • 样例输出
  • 3
14
  • 提示
  • 无
  • 来源
  • 2018暑期集训出题练习
  • 操作

显示春菜