Maximum Coins Collection in a Grid

Problem Statement:

You are given a 2D grid of size \(N \times M\) where each cell contains a non-negative integer representing the number of coins available at that cell. Starting from a given cell \((x_1, y_1)\), you can move in any of the four cardinal directions (up, down, left, right) with each move costing 1 step. You are allowed to take at most \(K\) steps. Your task is to compute the maximum number of coins you can collect by moving at most \(K\) steps. Note that you pick up the coin value every time you visit a cell (including the starting cell), and revisiting a cell will add its coin value again.

Details:

• The movement is allowed only in the four cardinal directions.
• You accumulate coins starting from the initial cell.
• There is no restriction on revisiting cells.

Solve the problem using an algorithm that explores all possible moves within \(K\) steps (for example, using Breadth First Search) and outputs the maximum coins collected.

inputFormat

Input Format:

1. The first line contains two integers \(N\) and \(M\) denoting the number of rows and columns of the grid, respectively.
2. The next \(N\) lines contain \(M\) integers each, representing the grid where each integer is the number of coins at that cell.
3. The last line contains three integers \(x_1\), \(y_1\), and \(K\) where \((x_1, y_1)\) denotes your starting position (0-indexed) and \(K\) is the maximum number of steps allowed.

Input is read from standard input (stdin).

outputFormat

Output Format:

Output a single integer representing the maximum number of coins that can be collected within \(K\) steps. The output should be written to standard output (stdout).

## sample

4 4
0 0 0 0
0 1 1 0
0 1 0 0
0 0 0 0
1 1 2

2

</p>