SAC '22 Code Challenge 2 P4 - Cookie Galore

View as PDF

Submit solution


Points: 10
Time limit: 1.0s
Python 4.0s
Memory limit: 256M

Author:
Problem type

After dealing with his N by M grid for too long, Santa asks you to find the minimum number of cookies he must eat to travel from (1, 1) to (N, M).

He can also only travel to cells that share a side with his current cell (i.e., not diagonally).

Each cell can either be an open space, denoted by ., or a cookie, denoted by C.

Whenever he enters a cell with a cookie, he always eats it.

Since Santa wants to maintain his slim figure, help him find the minimum number of cookies he needs to eat to travel from the top-left corner to the bottom-right corner!

Input Specification

The first line will contain N (1 \leq N \leq 1\,000) and M (1 \leq M \leq 1\,000), the number of rows and the numbers of columns in his grid.

The next N lines will each contain M cells.

Output Specification

Output the minimum amount of cookies that must be collected to travel from (1, 1) to (N, M).

Sample Input 1

6 4
C..C
.CCC
CC.C
..CC
CC..
C.C.

Sample Output 1

3

Sample Input 2

5 5
.....
..CC.
.....
.....
.....

Sample Output 2

0

Comments

There are no comments at the moment.