問題一覧 > 通常問題

No.3599 Queen Moving Query

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 31
作問者 : 👑 AngrySadEight / テスター : gomaazarasi ぽえ
お気に入りにしたユーザー ProblemId : 13441 / 自分の提出
問題文最終更新日: 2026-07-16 08:43:44
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
yukicoder contest 506 裏・クイーンコンテスト (順位表) の他の問題:

Problem Statement

There is a grid with $H$ rows and $W$ columns. The cell at the $i(1 \leq i \leq H)$-th row from the top and the $j(1 \leq j \leq W)$-th column from the left is denoted by cell $(i, j)$.

The state of this grid is given by $H$ strings $S_1, S_2, \dots, S_H$. Each string has length $W$. If $S_{i, j}$ is #, a wall is placed on cell $(i, j)$; if $S_{i, j}$ is ., no wall is placed on cell $(i, j)$.

Initially, $1$ queen piece is placed on cell $(sx, sy)$. This queen piece can freely enter and leave cells within the grid that have no wall, but it cannot enter or leave cells with a wall or cells outside the grid.

You are given $Q$ queries. The $i$-th query is as follows.

  • You are given $gx_i, gy_i, T_i$. Determine whether it is possible to move the queen piece so that the following condition is satisfied.
  • Starting from the initial state where the queen piece is on cell $(sx, sy)$, perform the following move operation exactly $T_i$ times. After the $T_i$ move operations are finished, the queen piece is on cell $(gx_i, gy_i)$.
    • Choose $1$ cell reachable in $1$ move from the cell where the queen piece currently is, and move the queen piece to the chosen cell. If there is no cell reachable in $1$ move, this operation cannot be performed.
How the queen piece moves (click to open)

In $1$ move, the queen piece can advance any number of cells in a vertical, horizontal, or diagonal direction, as long as all cells on its path can be entered and left. However, staying on the current cell does not count as $1$ move. Formally, a queen piece on cell $(i, j)$ can move as follows.

  • For a positive integer $k$, it can move to cell $(i, j + k)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i, j + l)$ is a cell the queen piece can enter and leave.
  • For a positive integer $k$, it can move to cell $(i, j - k)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i, j - l)$ is a cell the queen piece can enter and leave.
  • For a positive integer $k$, it can move to cell $(i + k, j)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i + l, j)$ is a cell the queen piece can enter and leave.
  • For a positive integer $k$, it can move to cell $(i - k, j)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i - l, j)$ is a cell the queen piece can enter and leave.
  • For a positive integer $k$, it can move to cell $(i + k, j + k)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i + l, j + l)$ is a cell the queen piece can enter and leave.
  • For a positive integer $k$, it can move to cell $(i + k, j - k)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i + l, j - l)$ is a cell the queen piece can enter and leave.
  • For a positive integer $k$, it can move to cell $(i - k, j + k)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i - l, j + l)$ is a cell the queen piece can enter and leave.
  • For a positive integer $k$, it can move to cell $(i - k, j - k)$ if and only if the following condition is satisfied.
    • For every integer $l$ satisfying $1 \leq l \leq k$, cell $(i - l, j - l)$ is a cell the queen piece can enter and leave.

Constraints

  • $H, W, sx, sy, Q, gx_i, gy_i, T_i$ are integers.
  • $H, W \geq 2$
  • $H \times W \leq 10^5$
  • $1 \leq sx \leq H$
  • $1 \leq sy \leq W$
  • $1 \leq Q \leq 10^5$
  • $1 \leq gx_i \leq H$
  • $1 \leq gy_i \leq W$
  • $1 \leq T_i \leq 10^9$
  • $S_i$ is a string of length $W$ consisting of # or ..
  • $S_{sx, sy}$ is ..
  • $S_{gx_i, gy_i}$ is ..

Input

The input is given from standard input in the following format.

$H$ $W$ $sx$ $sy$
$S_1$
$S_2$
$\vdots$
$S_H$
$Q$
$gx_1$ $gy_1$ $T_1$
$gx_2$ $gy_2$ $T_2$
$\vdots$
$gx_Q$ $gy_Q$ $T_Q$

Output

Output $Q$ lines. On the $i$-th line, output Yes if, in the $i$-th query, the queen piece can be placed on cell $(gx_i, gy_i)$ after exactly $T_i$ moves, and No otherwise.

Sample

Sample 1
Input
4 4 1 1
..##
.#..
..#.
#...
12
3 4 1
3 4 2
3 4 3
3 4 4
4 3 1
4 3 2
4 3 3
4 3 4
4 4 1
4 4 2
4 4 3
4 4 4
Output
No
Yes
Yes
Yes
No
Yes
Yes
Yes
No
No
Yes
Yes

For example, cell $(3, 4)$ can be reached from cell $(1, 1)$ in $2$, $3$, and $4$ moves respectively as follows.

  • $2$ moves: $(1, 1) \rightarrow (1, 2) \rightarrow (3, 4)$
  • $3$ moves: $(1, 1) \rightarrow (1, 2) \rightarrow (2, 3) \rightarrow (3, 4)$
  • $4$ moves: $(1, 1) \rightarrow (1, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)$

There is no way to reach cell $(3, 4)$ from cell $(1, 1)$ in $1$ move.

Sample 2
Input
2 2 1 1
..
#.
3
2 2 999999998
2 2 999999999
2 2 1000000000
Output
Yes
Yes
Yes

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。