Skip to content

14166: 【原4166】密室

题目

题目描述

author: Konpaku 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4166

Description

你身处在一间密室当中,这间密室由\(n*m\)个房间组成,每个房间都有一个编号。房间中有一个箱子,每个箱子中都有一把钥匙。编号为\(i\)的房间中的箱子要由编号为\(i-1\)的房间中的箱子中的钥匙来打开。编号为\(p\)的房间的箱子中存放着密室出口的钥匙。
你现在位于第一行第一列,手持可以打开编号为\(1\)的房子中的箱子的钥匙。从第\(a\)行第\(b\)列到第\(c\)行第\(d\)列需要花费\(|a-c|+|b-d|\)的时间。你想求出最少需要多少时间可以获得出口钥匙。

Input Format

由于一些奥妙重重的原因,你会连续陷入\(T(T<=3)\)个密室中。
第一行一个整数\(T\),意义如上
接下来有\(T\)个密室
每个密室第一行有三个整数\(n,m,p\) 接下来\(n\)行每行\(m\)个整数表示房间的编号
数据保证可以得到出口钥匙
保证编号为\(p\)的房间只有一间

Output Format

输出包括\(T\)行,每行一个整数表示最少时间

Sample Input

2
3 4 3
2 1 1 1
1 1 1 1
2 1 1 3
3 3 9
1 3 5
8 9 7
4 6 2

Sample Output

5
22

Data Range

对于100%的数据,\(T<=3,m<=300,p<=n*m\)。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!