Pingvin
레이팅 미적용의견: 0
Zrakoplović the penguin wants to learn how to fly!
The space in which he will learn to fly can be imagined as a cube of dimensions
\(n \times n \times n\), divided into \(n\)^{3} unit cubes. Each unit cube can be described with
three coordinates (x, y, z), where \(x\), \(y\) and \(z\) are integers between 1 and \(n\). The
coordinate \(x\) denotes the distance from the left edge of the space, the coordinate \(y\)
denotes the distance from the front edge of the space, and the coordinate \(z\) denotes
the height.
Some of these unit cubes contain clouds, and some do not.
Zrakoplović is afraid of clouds, so he will learn to fly only where there are no clouds. He initially finds
himself at a position (\(x@@RISE_MATH_BLOCK_0@@s = 1\) (i.e. at height 1), and wants to get to position (\(x\)\(e\), y\(e\), z\(e\)).
At the moment, he is perfecting the skill of flying in directions that are parallel to one of the axes of space
(i.e. in the direction of the \(x-ax\)is, \(y-ax\)is or \(z-ax\)is), and in one wing flap he can cross at most one unit
cube.
Before he decides to fly, Zrakoplović wants to know how many wing flaps he needs to get to the desired
position. While he is preparing for the flight, help him answer that question.
Subtask 1 (7 points): \(n = 2\)
Subtask 2 (16 points): There are no clouds.
Subtask 3 (22 points): All positions with \(z-co\)ordinate greater than 1 will be clouds.
Subtask 4 (25 points): No additional constraints.
The first line contains an integer \(n\) (\(1 \le n \le 100\)), the dimension of the space in which Zrakoplović learns
to fly.
The second line contains three integers \(x@@RISE_MATH_BLOCK_0@@s\) and \(z@@RISE_MATH_BLOCK_1@@s\), y\(s \le n\), z\(s = 1\)), the start position of
Zrakoplović.
The third line contains three integers \(x@@RISE_MATH_BLOCK_2@@e\) and \(z@@RISE_MATH_BLOCK_3@@e\), y\(e\), z\(e \le n\)), the end position of Zrakoplović.
This is followed by \(n\) binary matrices of dimensions \(n \times n\) that describe the space, where the \(i-th\) matrix
describes the space at height \(i\). The upp\(er-le\)ft corner has the coordinates (1, 1, i). The row and column of
the matrix correspond to the \(x\) and \(y\) coordinates, respectively.
’0’ denotes a unit cube in which there are no clouds, and ’1’ denotes a unit cube in which there are
clouds.
The start and end position of Zrakoplović will not be a cloud.
In the first and only line, print the smallest number of wing flaps that Zrakoplović must make to reach
the desired position. If Zrakoplović cannot reach the desired position, print ’-1’.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
1 | 7점 | \(n = 2\) |
2 | 16점 | There are no clouds. |
3 | 22점 | All positions with \(z-co\)ordinate greater than 1 will be clouds. |
4 | 25점 | No additional constraints. |
2
1 1 1
1 1 2
00
10
01
0013
2 3 1
1 1 1
000
010
000
111
111
111
111
111
11133
2 1 1
3 2 2
000
010
110
010
001
001
101
110
0003Clarification of the first example:
Zrakoplović can reach the desired position in one wing flap by moving in the direction of the z-axis for
one unit cube.
Clarification of the third example:
Zrakoplović can reach the desired position in three wing flaps by first moving to position (2, 1, 2), then to
(2, 2, 2) and finally to (3, 2, 2).
평가 및 의견
Pingvin
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
Pingvin