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

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

Sample Output 1


Sample Input 2

5 5

Sample Output 2



There are no comments at the moment.