← 返回题目列表

Codeforces · 1089/M

M. 雷图

中文机器翻译题面 查看原题

以下页面来自赛事官方发布的原题PDF,已完整保存并渲染到本地。

Minegraphed - 原题 PDF 第 1 页
原题PDF第15页
可复制的 PDF 提取文本
ICPC 2018 2019, NEERC   Northern Eurasia Finals, Online Mirror
                         St. Petersburg   Barnaul   Tbilisi   Almaty, December 2, 2018
Problem M. Minegraphed

Marika is developing a game called Minegraphed  that involves moving around a 3D rectangular world.

Each cell of a parallelepiped game  eld is either an empty cell or an obstacle cell. You are always standing
inside an empty cell, located either in the bottommost layer or on top of an obstacle cell. Each move can
be made in one of four directions: north, east, south, or west. You make a move according to these rules:

   •  If you try to move outside of the parallelepiped, then you can't make this move.
   • Otherwise, if the cell in front of you is empty, then you move one cell forward and then fall towards
     the bottom until you reach the bottommost layer or an obstacle cell.
   • Otherwise, if you are in non-topmost layer, the cell in front of you is an obstacle, the cell above you
     and the cell above that obstacle are both empty, then you move (climb up) on top of that obstacle.
   • Otherwise, you can't make this move.

Marika prepared a directed graph with n vertices. Now she wants to lay out the  eld and label n di erent
possible standing positions with numbers from 1 to n, so that it is possible to get from the cell labeled i
to the cell labeled j by making valid moves if and only if in Marika's graph it is possible to get from
vertex i to vertex j along the edges of the graph. Help Marika design a  eld satisfying this property.

Input

The  rst line contains a single integer n (1 ≤n ≤9)   the number of vertices. Each of the next n lines
contains n integers equal to 0 or 1. The j-th number in the i-th line is 1 if there is an edge from vertex i
to vertex j and 0 otherwise. The i-th number in the i-th line is always zero.

Output

Output a layer-by-layer description of a  eld that has the same reachability as the given graph.

The  rst line should contain three positive integers x, y, and z, the west-east, north-south, and top-bottom
sizes of the designed parallelepiped. Blocks describing z layers should follow, from the topmost layer to
the bottommost layer, separated by single empty lines. Each block should contain y lines of length x,
consisting of dots (`.'), hashes (`#'), and digits from 1 to n. A hash denotes an obstacle cell. A dot denotes
an unlabeled empty cell. A digit denotes a labeled empty cell. Each digit from 1 to n should appear
exactly once. Each digit should be located either in the bottommost layer or on top of an obstacle cell. It
is okay for obstacles to be hanging in the air  (there is no gravity for them).
The volume of the  eld x×y ×z should not exceed 106. It is guaranteed that there is a correct  eld  tting
into this limit for any possible graph in the input.

Example

   standard input     standard output                   Illustration
 4                   4 2 3
 0 1 0 1             ..#.
 0 0 1 0             .4..
 0 1 0 0           4
 1 0 0 0             ####                                                      1        2
                     1#.#     1
               3
                     ..3.      2                      4        3
                     #2..

Note

Note that you can climb up from cell 1 to cell 4, but you cannot climb up from cell 2 to cell 1 because of
a  ceiling  obstacle.


                                        Page 15 of 15