The Gnome and the Coins
In a rectangular matrix of size N x M, a labyrinth is represented. Each cell in the matrix is characterized by an integer:
- 0 indicates a free cell that can be traversed. - 1 represents an obstacle, an impassable cell. - 2 denotes a free cell containing one gold coin.
The labyrinth's entrance is at the free cell with coordinates (1,1), and the exit is at the free cell (N,M). The gnome starts at the entrance and must reach the exit within a limited time of K minutes. The gnome can move to adjacent free cells by crossing their shared side, taking 1 minute to traverse each cell. The number of gold coins in the labyrinth and the available time are both limited, for instance, to the number 10.
Why not make the journey more rewarding? The gnome can collect all the coins from the cells he visits. What is the maximum number of coins the gnome can gather under these conditions?
Input: The first line contains three numbers: N, M — the dimensions of the matrix (1<=N,M<=50) and K (1<=K<=100). The following N lines each contain M numbers, detailing the labyrinth's layout.
Output: A single number — the maximum number of coins the gnome can collect, or -1 if the gnome cannot complete the task.