Steve is mining for diamonds!

He is mining in a 2-block wide mineshaft and surprisingly does not care about falling into lava so is mining straight down. If he starts at the very top of the mineshaft, Steve wants to know how many blocks of stone he will need to mine in order to reach the bottom of the mineshaft. Blocks of stone are represented by the character "#", and empty spaces are represented by "." Steve can only move to another block if the other block is empty and is directly horizontally or vertically adjacent to the previous block. If the next block contains stone, then Steve would have to mine that block with his pickaxe. For example,

`.#`

A#

.#

B#

In the above diagram, if Steve is in the cell marked with `A`

, he can move to cell `B`

without mining anything by going through the empty cell in between `A`

and `B`

. However, in these diagrams,

`##`

A#

##

B#

##

`##`

A#

#B

##

In both of the above diagrams, Steve will have to mine at least one block of stone in order to go from `A`

to `B`

.

The mineshaft is depicted as a grid of width 2 and height N (1 ≤ N ≤ 200000).

The first line will contain the number `N`

. The next `N`

lines will contain the mine as a grid with height `N`

and width 2.

Print one integer: The least number of blocks Steve needs to mine in order to reach the bottom of the mineshaft, if he starts from above the mineshaft.

Subtask 1 (Worth 10 points): Each level of the mine will either contain two blocks of stone, or no blocks of stone (Either `##`

or `..`

).

Subtask 2 (Worth 20 points): 1 ≤ N ≤ 20

Subtask 3 (Worth 70 points): No additional constraints

`5`

..

..

..

..

..

`0`

`6`

##

.#

.#

#.

..

##

`3`

- Points: 7
- Time limit: 2.25s
- Memory limit: 128.0M
- Author: jimmyliu
- Category: Classics
- Type: Implementation, Greedy Algorithms
- All Submissions Best Submissions

Comments

- There are no comments.