A83318.逃离丛林

普及-

官方

通过率:0%

时间限制:1.00s

内存限制:128MB

题目描述

小明陷入了一片神秘的丛林之中,但是好在他可以借助树干的年轮来大致的判断方向。(年轮密集的是北方,年轮稀疏的方向是南方)。

这片丛林可以看做是一个 n×mn \times m的矩阵, 虽然没有这片丛林的地图,但是小明知道只要只要往一个方向一直不断的走,就可以走出这片迷雾森林。

然而不幸的是,这片丛林实际上是一片陷入了循环的空间,换句话说:

如果小明现在在第一行,那么他再向上走一格之后,就会到第 nn 行;
如果小明现在在第 nn 行,那么他往下走一格之后,就会到第 11 行。
如果小明现在在第 11 列,那么往左边走一格之后,就会到达第 mm 列;
如果小明现在在第 mm 列,那么向右走一格之后,则会到达第 11 列。

好在森林里的精灵愿意无声地帮助小明, 小明现在正在坐标(x,y)(x, y), 每当他到达一次坐标(i,j)(i, j), 就能获得一次该点的灵气值,当灵气值的总和大于等于 kk 时,精灵会把小明直接传送回家。

现在小明计划向东或者向南出发,也就是向右走或者向下走, 请你帮助可怜的小明计算一下两种方案分别需要走几步才能离开这片丛林?

输入格式

第一行输入 55 个整数,n,m,x,y,kn , m, x, y, k ,分别代表丛林的行数,列数,出发点的行坐标,列坐标, 离开丛林需要累计的灵气值。

(1n,m1000,1xn,1ym,1k1018)(1 \le n, m \le 1000, 1 \le x \le n, 1 \le y \le m, 1 \le k \le 10^{18})

接下来 nn 行, 每行 mm个整数, 代表整个丛林每一个位置到达时可获得的灵气值 ai,ja_{i,j}(1aij106)( 1 \le a_{ij} \le 10^6)

输出格式

输出两个数字,分别是向东走和向南走的方案下,需要几步才能离开这个丛林。

输入输出样例

  • 输入#1

    3 3 2 3 14
    1 4 3
    1 3 1
    4 1 1

    输出#1

    8 8

说明/提示

小明最开始站在出发点(x,y)(x, y) 上时,该点不提供灵气值, 但是如果下一次再经过坐标 (x,y)(x, y),那么就会获得对应的灵气值。

首页