問題一覧 > 通常問題

No.2843 Birthday Present Struggle

レベル : / AI推定難易度 : 700 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 135
作問者 : 👑 AngrySadEight / テスター : 👑 p-adic torisasami4
お気に入りにしたユーザー ProblemId : 11113 / 自分の提出
問題文最終更新日: 2024-08-23 16:41:13
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 441 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。