Preparando MOJI
Little Petya loves playing with rectangles. Mom bought Petya a rectangle divided into cells n × m in size (containing n rows, m columns). Petya marked two different cells of the rectangle and now he is solving the following task:
Let's define a simple path between those two cells as a sequence of distinct cells a1, a2, ..., ak, where a1 and ak are the two marked cells. Besides, ai and ai + 1 are side-neighboring cells of the path (1 ≤ i < k). Let's denote the path length as number k (the sequence length).
Petya's task is to find the longest simple path's length and to print the path. Help him.
The first line contains space-separated integers n and m (4 ≤ n, m ≤ 1000) — the number of rows and the number of columns in the rectangle, correspondingly. The second line contains space-separated integers x1 and y1 — the coordinates of the first marked cell. The third line contains space-separated integers x2 y2 — the coordinates of the second marked cell (1 < x1, x2 < n, 1 < y1, y2 < m, x1 ≠ x2, y1 ≠ y2).
The coordinates of a marked cell are a pair of integers x y, where x represents the row's number and y represents the column's number. The rows are numbered from top to bottom with consecutive integers from 1 to n. The columns are numbered from the left to the right by consecutive integers from 1 to m.
It is guaranteed that the marked cells are not positioned in one row or column.
In the first line print the length of the found path — k. In the next lines print k pairs of integers, one per line — coordinates of the cells that constitute the found path in the order, in which they follow in the path (the path must go from cell (x1, y1) to cell (x2, y2)). If there are several solutions, print any of them.
4 4
2 2
3 3
15
2 2
1 2
1 1
2 1
3 1
4 1
4 2
4 3
4 4
3 4
2 4
1 4
1 3
2 3
3 3
The statement test is described in the picture:
Informação
Provedor Codeforces
Código CF111E
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 08:32:40
Relacionados