No.1949 A Puzzle Game Where You Just Add (2)
Problem Statement
DHMO got curious about an ad for yet another puzzle game that played when continuing in a puzzle game, so they decided to play it.
The puzzle game is a game in which you move a player within a grid of $H$ rows and $W$ columns. The cell in the $i$-th row from the top and the $j$-th column from the left is called $(i,j)$. Cells that do not satisfy ($1 \le i \le H$ and $1 \le j \le W$) do not exist.
The player is initially at $(Y,X)$, and their attack power is $A_{Y,X}$.
There is an enemy on every cell other than $(Y,X)$, and the attack power of the enemy at $(i,j)$ is $A_{i,j}$.
The game is cleared when all enemies have been defeated.
When the player is at $(i,j)$, they can move to any existing cell among $(i+1,j), (i,j+1), (i-1,j), (i,j-1)$.
The player then battles the enemy on the destination cell.
If the player's attack power is higher than the enemy's attack power, the player defeats the enemy, and the player's attack power increases by the enemy's attack power.
If the player's attack power is less than or equal to the enemy's, the player loses and the game is over.
The player may pass through the same cell any number of times, but a defeated enemy does not revive, and no battle takes place when visiting a cell that has already been passed through.
The contents of the puzzle game are given as input.
Determine whether the game can be cleared by operating the player appropriately.
Input
$H$ $W$ $Y$ $X$
$A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,W}$
$A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,W}$
$\vdots$
$A_{H,1}$ $A_{H,2}$ $\ldots$ $A_{H,W}$
Constraints
- $ 2 \le H,W \le 500$
- $ 1 \le Y \le H$
- $ 1 \le X \le W$
- $ 1 \le A_{i,j} \le 10^{9}$
- All inputs are integers.
Output
Print Yes if the game can be cleared, and No otherwise.
Print a newline at the end.
Sample
Sample 1
Input
3 4 2 1 10 8 15 50 5 4 40 50 10 1 30 60
Output
Yes
You can clear the game by moving as shown in the image. You may pass through the same cell any number of times, and you may defeat the enemies in any order.
Sample 2
Input
2 5 2 2 10 5 50 10 30 10 10 50 50 20
Output
No
The game cannot be cleared no matter how you move.
Sample 3
Input
2 2 1 1 10 2 1 12
Output
Yes
You can clear the game by moving as $(1,1) → (1,2) → (1,1) → (2,1) → (2,2)$.
Sample 4
Input
5 5 5 5 3 2 2 5 20 2 8 1 3 10 9 4 20 40 10 8 7 32 22 88 20 13 26 51 100
Output
Yes
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
H20
蜜蜂
naskya