| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 84 | 27 | 23 | 33.824% |
A space station is made up of cubic modules arranged in a 25ドル \times 25 \times 25$ grid. The position of each module in the grid is indicated by its X-, Y-, and Z-coordinates with integer values in the range 1ドル \ldots 25$. Any pair of modules next to each other along the X-, Y-, or Z-axis is connected by a tunnel. Each tunnel has doors at both ends. If both doors are open, air may flow between the two modules.
One of the modules has been damaged and leaks air into the space. Air is also being lost from all those modules from which it can flow to the damaged module, either directly or via other modules. Find all the modules that are losing air. You may assume that the doors of the damages module still work correctly.
The first line contains $U,ドル the number of open doors in the station (1ドル \le U \le 10,000円$). Each of the following $U$ lines describes one open door: the coordinates of the module and the direction of the door (the name of the axis and '+' for the direction of increasing values of the coordinate, or '-' for the decreasing direction). The last line contains the coordinates of the damaged module.
Output the coordinates of all the modules that are losing air, each module on a separate line. Order the lines in ascending order first by the Z-, then by the Y-, and finally by the X-coordinates.
5 2 1 1 X- 1 1 1 X+ 1 1 1 Z+ 3 1 1 X- 1 1 2 Z- 1 1 1
1 1 1 2 1 1 1 1 2
The corner module $(1; 1; 1)$ is damaged. This module has doors open in the increasing direction of the X- and Z-coordinates. The next module along the X-axis, $(2; 1; 1),ドル has the door in the decreasing direction of the X-coordinate open, so air can flow to the damaged module. The situation is similar with $(1; 1; 2),ドル the neighbor of the damaged module along the Z-axis. The module $(3; 1; 1)$ is not losing air, because the door in the increasing direction of the X-axis in the module $(2; 1; 1)$ is closed. The module $(1; 1; 2)$ is listed last in the output, because the Z-coordinate has the first priority when sorting.