No.323 yuki Country
タグ : / 解いたユーザー数 114
作問者 :
ぴろず
Note
This problem was created as the problem for day 16 of the Advent Calendar Contest Advent Calendar 2015.
The writer confirmed that it can be AC'd with plenty of margin in Java and PyPy2, but it got TLE in Python2.
If you are using a relatively slow language, please be careful about the execution time.
Problem Statement
Taro is building a snowman in a rectangular vacant lot, and he is currently rolling a snowball.
The lot is represented as a grid with $H$ rows and $W$ columns. The cell in row $i(0 \leq i \leq H-1)$ and column $j(0 \leq j \leq W-1)$ is called cell $(i,j)$.
Initially, the snowball is at cell $(S_i,S_j)$ and its size is $A$.
Taro can move the snowball to an adjacent cell in one of the four directions: up, down, left, or right. However, it must not leave the lot.
When this happens, the size of the snowball increases by $1$ if the destination cell has snow on it, and decreases by $1$ otherwise.
If the size of the snowball becomes $0$ or less, the snowball melts. That is, the size of the snowball must always be at least $1$.
Determine whether Taro can bring the snowball to cell $(G_i,G_j)$ with its size being exactly $B$.
Input
$H$ $W$
$A$ $S_i$ $S_j$
$B$ $G_i$ $G_j$
$M_0$
$M_1$
$\vdots$
$M_{H-1}$
The $1$st line contains two integers $H$,$W$ separated by a space.
The $2$nd line contains three integers $A$,$S_i$,$S_j$ separated by spaces.
The $3$rd line contains three integers $B$,$G_i$,$G_j$ separated by spaces.
The $H$ lines starting from line $4$ contain strings $M_0 \dots M_{H-1}$ of length $W$.
If the $j(0 \leq j \leq W-1)$-th column of $M_i$ is '*' (asterisk), cell $(i,j)$ has snow on it.
If it is '.' (period), cell $(i,j)$ has no snow on it.
$1 \leq H,W \leq 50$
$1 \leq A,B \leq 1000$
$0 \leq S_i,G_i \leq H-1$
$0 \leq S_j,G_j \leq W-1$
$(A,S_i,S_j) \neq (B,G_i,G_j)$
$M_i(0 \leq i \leq H-1)$ is a string of length $W$ consisting only of '*' (asterisk) and '.' (period).
Output
Print 'Yes' if Taro can bring the snowball to cell $(G_i,G_j)$ with its size being exactly $B$, and 'No' otherwise.
Print a newline at the end.
Sample
Sample 1
Input
2 4 2 0 0 2 1 3 *.*. .*.*
Output
Yes
For example, moving right, right, right, down reaches the target cell, and the size of the snowball becomes 2.
The size of the snowball changes as $2$→$1$→$2$→$1$→$2$.
Sample 2
Input
2 1 1 0 0 4 1 0 * *
Output
Yes
Moving $3$ times, down, up, down, reaches the target cell, and the size of the snowball becomes 4.
The snowball is at the target cell after the first move down, but its size is not yet sufficient at that point.
Sample 3
Input
4 4 3 3 0 8 0 3 .*** ..** ...* ....
Output
No
The size of the snowball must not become 0 or less along the way, so it cannot reach the target cell.
Sample 4
Input
8 10 1 1 4 5 1 4 ....*.*.*. .........* .......... .*.*.*...* *...**.... .........* *......... .*.*.*.*.*
Output
Yes
The cell where the snowball is initially located and the target cell may be the same.
Sample 5
Input
1 10 1 0 0 6 0 9 **......**
Output
Yes
Sample 6
Input
4 5 5 1 1 6 1 3 .*..* *.... *...* ****.
Output
No
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。