問題一覧 > 通常問題

No.3599 Queen Moving Query

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 26
作問者 : 👑 AngrySadEight / テスター : gomaazarasi ぽえ
ProblemId : 13441 / yukicoder contest 506 裏・クイーンコンテスト (順位表) / 自分の提出
問題文最終更新日: 2026-07-16 08:43:44
yukicoder contest 506 裏・クイーンコンテストの他の問題:

問題文

縦 $H$ マス，横 $W$ マスのマス目があります．上から $i(1 \leq i \leq H)$ 番目，左から $j(1 \leq j \leq W)$ 番目のマスを，マス $(i, j)$ と表記します．

このマス目の状態が，$H$ 個の文字列 $S_1, S_2, \dots, S_H$ で与えられます．各文字列の長さは $W$ で，$S_{i, j}$ が # ならばマス $(i, j)$ に壁が置かれていることを，$S_{i, j}$ が . ならばマス $(i, j)$ に壁が置かれていないことを表します．

最初，マス $(sx, sy)$ に，クイーンのコマが $1$ 個置かれています．このクイーンのコマは，マス目の範囲内のマスのうち，壁の置かれていないマスに自由に出入り可能ですが，壁の置かれているマスや，範囲外のマスには出入りできません．

クエリが $Q$ 個与えられます．$i$ 番目のクエリの内容は以下の通りです．

  • $gx_i, gy_i, T_i$ が与えられる．次に示す条件を満たすようなクイーンのコマの移動が可能かどうか判定せよ．
  • マス $(sx, sy)$ にクイーンのコマが置かれている最初の状態から，次に示す移動操作を，ちょうど $T_i$ 回行う．$T_i$ 回の移動操作終了後，クイーンのコマはマス $(gx_i, gy_i)$ に置かれている．
    • 今クイーンのコマがいるマスから $1$ 回の移動で到達可能なマスを $1$ つ選び，クイーンのコマを選んだマスに移動させる．$1$ 回の移動で到達可能なマスがない場合は，この操作は行えない．
クイーンのコマの移動方法について（クリックで開く）

クイーンのコマは，$1$ 回の移動において，縦・横・斜めの方向に，通る経路のマスが全て出入り可能である限り自由なマス数進むことができます．ただし，今いるマスにとどまることを $1$ 回の移動とみなすことはできません．厳密には，マス $(i, j)$ にあるクイーンのコマは次のような移動が可能です．

  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i, j + k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i, j + l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i, j - k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i, j - l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j + k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j + l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i + k, j - k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i + l, j - l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j + k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j + l)$ はクイーンのコマが出入り可能なマスである．
  • 正整数 $k$ に対し，次の条件を満たしている場合，またそのときに限りマス $(i - k, j - k)$ への移動が可能である．
    • $1 \leq l \leq k$ を満たす全ての整数 $l$ に対し，マス $(i - l, j - l)$ はクイーンのコマが出入り可能なマスである．

制約

  • $H, W, sx, sy, Q, gx_i, gy_i, T_i$ は整数
  • $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$ は # または . からなる長さ $W$ の文字列
  • $S_{sx, sy}$ は .
  • $S_{gx_i, gy_i}$ は .

入力

入力は以下の形式で標準入力から与えられる．

$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$

出力

$Q$ 行出力せよ．$i$ 行目には，$i$ 番目のクエリにおいてちょうど $T_i$ 回の移動でマス $(gx_i, gy_i)$ にクイーンのコマが置かれているようにできるならば Yes を，そうでなければ No を出力せよ．

サンプル

サンプル1
入力
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
出力
No
Yes
Yes
Yes
No
Yes
Yes
Yes
No
No
Yes
Yes

例えば，マス $(1, 1)$ からマス $(3, 4)$ に，$2$ 回，$3$ 回，$4$ 回の移動でそれぞれ到達できる方法には以下があります．

  • $2$ 回の移動：$(1, 1) \rightarrow (1, 2) \rightarrow (3, 4)$
  • $3$ 回の移動：$(1, 1) \rightarrow (1, 2) \rightarrow (2, 3) \rightarrow (3, 4)$
  • $4$ 回の移動：$(1, 1) \rightarrow (1, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)$

マス $(1, 1)$ からマス $(3, 4)$ に $1$ 回の移動で到達できる方法はありません．

サンプル2
入力
2 2 1 1
..
#.
3
2 2 999999998
2 2 999999999
2 2 1000000000
出力
Yes
Yes
Yes

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