No.2843 Birthday Present Struggle
タグ : / 解いたユーザー数 135
作問者 : 👑
torisasami4
Problem Statement
A certain town has the shape of a grid with $N$ rows and $N$ columns. Each $1$ cell of the grid is called a "block", and the block in row $i$, column $j$ is called "block $(i, j)$".
The $3$ people Alice, Bob, and Charlie live in distinct blocks, no two of which are vertically or horizontally adjacent. Alice, Bob, and Charlie live in blocks $(a_x, a_y)$, $(b_x, b_y)$, and $(c_x, c_y)$, respectively. Also, for the block where any of the $3$ people lives, adjacent blocks exist in all four directions: up, down, left, and right.
Bob has decided to go to Alice's house on her birthday and give her a present.
Bob, who desperately wants to become close to Alice, has decided to place walls on some blocks of the town so that Charlie cannot reach Alice's house, preventing Charlie from giving Alice a present.
Specifically, he has decided to place walls so that the following conditions are satisfied.
- Bob's house can reach Alice's house by repeatedly moving to a vertically or horizontally adjacent cell without a wall.
- Charlie's house cannot reach Alice's house by repeatedly moving to a vertically or horizontally adjacent cell without a wall.
However, because of construction costs, Bob can place at most $N$ walls. Also, walls cannot be placed on a block containing the house of Alice, Bob, or Charlie.
Find one way of placing walls that satisfies the conditions. It can be shown that, under the constraints of this problem, a way of placing walls that satisfies the conditions exists.
Constraints
- All input values are integers.
- $5 \leq N \leq 1000$
- $2 \leq a_x, a_y, b_x, b_y, c_x, c_y \leq N - 1$
- $(a_x, a_y), (b_x, b_y), (c_x, c_y)$ are all distinct.
- No two of the blocks $(a_x, a_y), (b_x, b_y), (c_x, c_y)$ are vertically or horizontally adjacent. In other words, $|a_x - b_x| + |a_y - b_y| \neq 1, |a_x - c_x| + |a_y - c_y| \neq 1, |b_x - c_x| + |b_y - c_y| \neq 1$ holds.
Input
The input is given from standard input in the following format.
$N$ $a_x$ $a_y$ $b_x$ $b_y$ $c_x$ $c_y$
Output
Let $m$ be the number of walls placed, and let block $(x_i, y_i)$ be the block on which the $i$-th wall is placed. Output in the following format. Here, $m \leq N$ must hold, and the $(x_i, y_i)$ must all be pairwise distinct. Also, none of the $(x_i, y_i)$ may coincide with any of $(a_x, a_y), (b_x, b_y), (c_x, c_y)$.
$m$ $x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_m$ $y_m$
Sample
Sample 1
Input
5 2 2 4 2 4 4
Output
5 1 3 2 3 3 3 4 3 5 3
Walls are placed as shown in the figure below. The red, blue, and yellow blocks represent the blocks containing the houses of Alice, Bob, and Charlie, respectively, the black blocks represent the blocks on which walls are placed, and the white blocks represent all other blocks.
In this case, Bob can reach Alice's house, but Charlie cannot reach Alice's house.
Sample 2
Input
9 4 2 6 2 5 8
Output
9 3 1 3 2 3 3 4 3 5 3 6 3 7 3 7 2 7 1
Walls are placed as shown in the figure below.
Note that you do not need to minimize the number of walls placed.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。