No.3601 Queen Dist Sum with One Wall
タグ : / 解いたユーザー数 20
作問者 : 👑
gomaazarasi
ぽえ
Problem Statement
There is a grid with $H$ rows and $W$ columns. The square in 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 square $(i, j)$.
A wall is placed on $1$ square of this grid, namely square $(x, y)$. No walls are placed on the other squares.
Initially, $1$ queen piece is placed on square $(h, w)$. This queen piece can freely enter and leave the squares within the grid that have no wall, but it cannot enter or leave a square with a wall or a square outside the grid.
For integers $(i, j)$ satisfying $1 \leq i \leq H, 1 \leq j \leq W, (i, j) \neq (x, y)$, let $D(i, j)$ denote the minimum number of moves required to move the queen piece, initially on square $(h, w)$, to square $(i, j)$.
Find $\displaystyle\sum_{1 \leq i \leq H, 1 \leq j \leq W, (i, j) \neq (x, y)} D(i, j)$.
You are given $T$ test cases; answer each of them.
How the queen piece moves (click to expand)
In $1$ move, the queen piece can advance any number of squares in a vertical, horizontal, or diagonal direction, as long as all squares along the path can be entered and left. However, staying on the current square does not count as 1 move. Formally, a queen piece on square $(i, j)$ can move as follows.
- For a positive integer $k$, it can move to square $(i, j + k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, square $(i, j + l)$ is a square that the queen piece can enter and leave.
- For a positive integer $k$, it can move to square $(i, j - k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, square $(i, j - l)$ is a square that the queen piece can enter and leave.
- For a positive integer $k$, it can move to square $(i + k, j)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, square $(i + l, j)$ is a square that the queen piece can enter and leave.
- For a positive integer $k$, it can move to square $(i - k, j)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, square $(i - l, j)$ is a square that the queen piece can enter and leave.
- For a positive integer $k$, it can move to square $(i + k, j + k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, square $(i + l, j + l)$ is a square that the queen piece can enter and leave.
- For a positive integer $k$, it can move to square $(i + k, j - k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, square $(i + l, j - l)$ is a square that the queen piece can enter and leave.
- For a positive integer $k$, it can move to square $(i - k, j + k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, square $(i - l, j + l)$ is a square that the queen piece can enter and leave.
- For a positive integer $k$, it can move to square $(i - k, j - k)$ if and only if the following condition is satisfied.
- For every integer $l$ satisfying $1 \leq l \leq k$, square $(i - l, j - l)$ is a square that the queen piece can enter and leave.
Constraints
- All inputs are integers.
- $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)$
Input
The input is given from standard input in the following format. Here, $\mathrm{case}_i$ represents the $i$-th test case.
$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$
Each case is given in the following format.
$H$ $W$ $h$ $w$ $x$ $y$
Output
Print $T$ lines. The $i$-th line should contain the answer to the $i$-th test case.
Sample
Sample 1
Input
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
Output
9 2 969 1999997998404
For test case $1$, the value of $D(i, j)$ for each square $(i, j)$ is as shown in the figure below.
Therefore, the value of $\displaystyle \sum_{1 \leq i \leq 3, 1 \leq j \leq 3, (i, j) \neq (3, 1)} D(i, j)$ is $1 + 1 + 2 + 0 + 1 + 1 + 1 + 2 = 9$.
For test case $2$, $D(1, 1) = 0, D(1, 2) = 1, D(2, 1) = 1$, so the answer is $0 + 1 + 1 = 2$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。