問題一覧 > 通常問題

No.323 yuki Country

レベル : / AI推定難易度 : 1100 / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 114
作問者 : ぴろず
お気に入りにしたユーザー ProblemId : 845 / 自分の提出
問題文最終更新日: 2026-06-25 05:00:06
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
Advent Calendar Contest 2015 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。