#K68192. Exact Energy Path
Exact Energy Path
Exact Energy Path
You are given a square grid of size \(m \times m\) where each cell contains a non-negative integer. Starting from the top-left cell, you may only move right or down. As you travel, accumulate the values of the cells along your path. Your task is to determine if there exists a path from the top-left cell to the bottom-right cell such that the total accumulated sum is exactly equal to a given target energy \(E\).
The journey starts at cell (1,1) with an initial energy equal to the value in that cell. Upon reaching the bottom-right cell, the total energy consumed along the path must be equal to \(E\). If such a path exists, output YES
; otherwise, output NO
.
Note: Moves are only allowed to the right or downward.
inputFormat
The first line contains an integer \(T\), the number of test cases. Each test case is described as follows:
- The first line of each test case contains two integers \(m\) and \(E\), where \(m\) is the size of the grid and \(E\) is the target energy.
- The next \(m\) lines each contain \(m\) space-separated integers representing the grid.
For example:
2 3 7 0 1 2 1 1 3 4 2 1 4 15 1 2 3 4 2 3 4 5 3 4 5 6 4 5 6 7
outputFormat
For each test case, output a single line containing YES
if it is possible to reach the bottom-right cell using a path that precisely accumulates \(E\) energy. Otherwise, output NO
.
For the sample input above, the output should be:
YES NO## sample
2
3 7
0 1 2
1 1 3
4 2 1
4 15
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
YES
NO
</p>