oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

eventreasure Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

eventreasure.html

Little Joseph is in a maze and has to collect all the treasure in the maze. Since Little Joseph likes even numbers, any grid that is marked with an even number is a grid with a treasure.

However, the maze is constructed in such a way that he can only move right on even rows (row 0, 2, 4, etc) and move left on odd rows (row 1, 3, 5 etc). At any grid he can move down to the next row.

Starting at grid[0,0] and ending at any grid cell on the last row, what is the minimum number of moves he has to make (a move is a movement from one grid to another) to get from the start grid to the last grid and collecting all the treasure he can?

You are also given that every row will have at least one treasure in its grid.

Input

The first line consists of the maze width W and height H.

The next H lines consist of W digits (from 0 to 9) and this indicates the number on that grid.

Output

You are to output the minimum number of moves Little Joseph has to make to collect all the treasure he can.

Limits

For 30% of the test cases, W < 100, H < 100.

For 60% of the test cases, W < 1000, H < 1000.

For 100% of the test cases, W * H < 10000000.

Sample Input 1

5 3
14972
36721
31649

Sample Output 1

11

Explanation

He moves right from grid[0,0] to grid[0,4] (4 moves), moves down to grid[1,4] (1 move), moves left from grid[1,4] to grid[1,1] (3 moves), moves down to grid[2,1] (1 move) and lastly moves right from grid[2,1] to grid[2,3] (2 moves), making it a total of 11 moves.

Tags

Dynamic Programming

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110061s32MBAverage
2011s32MBAverage

Judge Compile Command

g++-8 ans.cpp -o eventreasure -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.