奇怪的电梯
该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
【题目描述】
小明是一个旅游爱好者,这次他来到了一座新的城市。
城市中央有一幢高耸入云的大楼。这幢楼到底有多少层呢?据说和非负整数的个数是一样多的。
小明想爬上这座大楼来观赏新城市的全景。这幢大楼的楼层从下至上用从小到大的非负整数编号。每层楼有 个房间,用 到 的正整数编号。楼层之间用电梯连接,电梯只能上行,不能下行或者同层移动。电梯用 的形式给出,表示对于任意整数 ,由第 层的房间 到第 层的房间 有一部电梯。电梯只能从起点开往终点,不能中途停留。
小明想要观赏城市全景,至少需要登上第 层楼,即最终需要到达的楼层数 。由于乘坐电梯要缴纳高额的费用,而如果花销太大回家就没法报账了,小明希望乘坐电梯的次数最少。现在小明在第 层的 号房间,你需要求出这个最少的乘坐次数。
【输入】
第一行包含一个正整数 ,表示数据的组数。
接下来的数据分为 个部分。每个部分:
- 第一行包含两个正整数 和 ,意义见题目描述。
- 接下来 行,每行包含 个非负整数。这 行中,第 行第 个数为 ,如果 非零,则表示有电梯 。同一行各个数之间均用一个空格隔开。
【输出】
对于每组数据,输出一行一个正整数,最少的乘坐次数。
【样例输入】
2
6 147
0 1 0 50 0 0
0 0 1 0 0 0
20 0 0 0 0 0
0 0 0 0 1 50
0 0 0 8 0 0
0 0 0 0 0 3
6 152
0 1 0 50 0 0
0 0 1 0 0 0
20 0 0 0 0 0
0 0 0 0 1 50
0 0 0 8 0 0
0 0 0 0 0 3
【样例输出】
9
10
【样例说明】
第一组数据中,依次到达的房间顺序为:0层1号 → 1层2号 → 2层3号 → 22层1号 → 23层2号 → 24层3号 → 44层1号 → 94层4号 → 144层6号 → 147层6号;
第二组数据中,依次到达的房间顺序为:0层1号 → 1层2号 → 2层3号 → 22层1号 → 23层2号 → 24层3号 → 44层1号 → 94层4号 → 95层5号 → 103层4号 → 153层6号。第二组数据最后到达了153层,但是没有更少的乘坐电梯次数使得恰好到达152层,因此答案为10。
【数据范围】
1、有10%的数据所有的 ;
2、有20%的数据 ;
3、有20%的数据对于满足 的整数 和 ,若 ,则有 ;
4、有30%的数据所有的 。
以上各类数据均不包含其他类数据。对于所有数据 ;对于满足 的整数 和 ,有 。数据保证能够到达 层或更高的楼层。