## Jumping

View as PDF

Points:17
Time limit:0.6s
Memory limit:64M
Authors:

Problem type

Allowed languages
C, C++

Pepe the frog needs to jump across a river while only stepping on some stones! He needs to jump from column to column (left to right in the input). Rock means the rock on row . However, jumping from row to takes time.

#### Input

The first line of the input contains two integers, and , the number of columns and the number of positions of rocks.

Each subsequent lines of the input contains of a string of 0s and 1s. A 1 on line (starting from 2nd line) on column (both 0-indexed) indicates the rock is present in column , a 0 indicates that rock is not present.

#### Output

Output the minimum amount of time taken to jump to the end.

You are guaranteed there is at least one possible way to jump to the end.

#### Sample Input 1

5 3
11100
00011
11111

#### Sample Output 1

0

#### Sample Input 1 Explanation

You don't need to jump, just use rock 3 throughout.

#### Sample Input 2

5 5
10000
01000
00100
00010
00001

#### Sample Output 2

4

#### Sample Input 2 Explanation

Start from rock 0, change to rock 1, change to rock 2, etc. Each of them takes 1 time because they are adjacent.

• kobortor
commented on Jan. 7, 2017
Time limit

The time constraint for this question is quite strict. It is not guaranteed to be solvable by languages other than C++. Even then you will need quite a bit of constant optimization to pass (assuming you have the optimal time complexity).

• gloomcore
commented on Jan. 7, 2017 edited
Some clarification will be helpful

Can frog jump back or just forward? And can frog move between different stones within the same column?

    11100
00100
00111

Is answer for this test is 2?

• bruce
commented on Jan. 7, 2017

Based on my submission, the frog can only jump forward. The case you provided is the same as

11000
00100
00011

and the answer is 2.

• gloomcore
commented on Jan. 9, 2017 edited

Thanks, a lot Bruce, it will help me clarify task. I wanted to check if frog can jump between diffrent rows on the same column. I mean, that if frog can jump between different rows on the same colum, then as for test:

1110000
0001000
0001000
0001000
0001000
0001000
0000111

the answer is 6, when frog will jump between different rows in the same column.

In other case, if frog should always move one column forward and cannot make jumps within the same column, then the best answer in this case is 18. (Jump from row 1 to row 4 and from row 4 to row 7).

Can you help, which way is correct?

• bruce
commented on Jan. 9, 2017

The frog cannot jump between different rows in the same column. Agree with ZQFMGB12. 18 is the best answer for your case.

• ZQFMGB12
commented on Jan. 9, 2017

The latter is correct.