問題一覧 > 通常問題

No.3601 Queen Dist Sum with One Wall

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

問題文

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

このマス目のうちの $1$ マス，マス $(x, y)$ には壁が置かれています．これ以外のマスには壁は置かれていません．

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

$1 \leq i \leq H, 1 \leq j \leq W, (i, j) \neq (x, y)$ を満たす整数 $(i, j)$ に対して，最初マス $(h, w)$ に置かれているクイーンのコマをマス $(i, j)$ に移動させるための移動回数の最小値を $D(i, j)$ と表します．

$\displaystyle\sum_{1 \leq i \leq H, 1 \leq j \leq W, (i, j) \neq (x, y)} D(i, j)$ を求めてください．

$T$ 個のテストケースが与えられるので，それぞれについて答えてください．

クイーンのコマの移動方法について（クリックで開く）

クイーンのコマは，$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)$ はクイーンのコマが出入り可能なマスである．

制約

  • 入力は全て整数
  • $1 \leq T \leq 10^5$
  • $2 \leq H, W \leq 10^6$
  • $1 \leq h, x \leq H$
  • $1 \leq w, y \leq W$
  • $(h, w) \neq (x, y)$

入力

入力は以下の形式で標準入力から与えられる．ここで，$\mathrm{case}_i$ は $i$ 番目のテストケースを表す．

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

各ケースは以下の形式で与えられる．

$H$ $W$ $h$ $w$ $x$ $y$

出力

$T$ 行出力せよ．$i$ 行目には，$i$ 番目のテストケースの答えを出力せよ．

サンプル

サンプル1
入力
4
3 3 2 1 3 1
2 2 1 1 2 2
20 26 7 24 8 1
1000000 1000000 2026 724 2026 801
出力
9
2
969
1999997998404

$1$ つ目のテストケースについて，各マス $(i, j)$ についての $D(i, j)$ の値は以下の図のようになります．

よって，$\displaystyle \sum_{1 \leq i \leq 3, 1 \leq j \leq 3, (i, j) \neq (3, 1)} D(i, j)$ の値は，$1 + 1 + 2 + 0 + 1 + 1 + 1 + 2 = 9$ となります．

$2$ つ目のテストケースについて，$D(1, 1) = 0, D(1, 2) = 1, D(2, 1) = 1$ なので答えは $0 + 1 + 1 = 2$ です．

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