{"problem":{"name":"01. Labyrinth-1","description":{"content":"You have a robot in a two-dimensional labyrinth which consists of _N_ × _M_ cells. Some pairs of cells adjacent by side are separated by a wall or a door. The labyrinth itself is separated from the ou","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":8000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF92101"},"statements":[{"statement_type":"Markdown","content":"You have a robot in a two-dimensional labyrinth which consists of _N_ × _M_ cells. Some pairs of cells adjacent by side are separated by a wall or a door. The labyrinth itself is separated from the outside with walls around it. Some labyrinth cells are the exits. In order to leave the labyrinth the robot should reach any exit. There are keys in some cells. Any key can open any door but after the door is opened the key stays in the lock. Thus every key can be used only once. There are no labyrinth cells that contain both a key and an exit. Also there can not be both a wall and a door between the pair of adjacent cells.\n\nYour need to write a program in _abc_ language (see the language description below) that will lead the robot to one of the exits. Lets numerate the labyrinth rows from 0 to _N_ - 1 top to bottom and the columns – from 0 to _M_ - 1 left to right.\n\nIn _abc_ language the following primary commands are available:\n\n*   _move-DIR_ – move to the adjacent cell in the direction. _down_ increases the number of the row by 1, _right_ increases the number of the column by 1. In case there’s a wall or a closed door in this direction, nothing’s happening.\n*   _open-DIR_ – open the door between the current cell and the adjacent one in _DIR_ direction. In case there isn’t any door in this direction or it’s already been opened or the robot doesn’t have a key, nothing’s happening.\n*   _take_ – take the key in the current cell. In case there isn’t any key or the robot has already picked it up, nothing’s happening. The robot is able to carry any number of keys.\n*   _terminate_ – terminate the program. This command is not obligatory to use. In case it’s absent the command is added at the end of the program automatically.\n\nAlso, there are the following control commands in _abc_ language:\n\n*   _for-N OPS end_ – repeat the sequence of the _OPS_ commands _N_ times, 0 < _N_ ≤ 100000. Each loop counter check counts as a command fulfilled by the robot.\n*   _if-ok OPS1 else OPS2 endif_ – carries out the sequence of the _OPS_1 commands, if the previous command of moving, taking the key or opening the door was successful, otherwise the sequence of the _OPS_2 commands is being carried out. Should there be no previous command run, the sequence _OPS_1 will be carried out. If-ok check counts as a command fulfilled by the robot.\n*   _break_ – stops the current _for_ loop.\n*   _continue_ – finishes the current _for_ loop iterations.\n\nNote that the control and the primary commands can be fit into each other arbitrarily.\n\nThe robot will fulfill your commands sequentially until it exits the labyrinth, or it runs out of the commands, or the _terminate_ command is run, or the quantity of the fulfilled commands exceeds the bound number 5·106.\n\nIn _abc_ language each command is a separate word and should be separated from other commands with at least one space symbol.\n\nYou should write a program that prints the sequence of commands leading the robot out of the labyrinth. Of course, as you are a good programmer, you should optimize these sequence.\n\nThe number of the non-space symbols in the sequence should not exceed 107. If you succeed in finding the way out of the labyrinth _i_ you’ll be granted the number of points equal to:\n\nwhere:\n\n*   _W__i_ – labyrinth’s weight, some fixed constant.\n*   _G__i_ – number of robots moves.\n*   _O__i_ – number of fulfilled commands. Note that this number includes commands like _take_ executed in the cells with no key, as well as opening commands applied to the already opened doors.\n*   _L__i_ – sequence length in symbols, excluding space symbols and line breaks.\n*   _Q_ = 10·_N_·_M_.\n\nIn case your sequence doesn’t lead the robot to the exit you’ll be granted 0 points. Your programs result will be the sum of all _S__i_. You should maximize this total sum.\n\nAll labyrinths will be known and available to you. You can download the archive with labyrinths by any of the given links, password to extract files is _aimtechiscool_:\n\n1.  [https://drive.google.com/file/d/1dkIBfW_Gy6c3FJtXjMXZPMsGKRyn3pzp](https://drive.google.com/file/d/1dkIBfW_Gy6c3FJtXjMXZPMsGKRyn3pzp)\n2.  [https://www.dropbox.com/s/77jrplnjgmviiwt/aimmaze.zip?dl=0](https://www.dropbox.com/s/77jrplnjgmviiwt/aimmaze.zip?dl=0)\n3.  [https://yadi.sk/d/JNXDLeH63RzaCi](https://yadi.sk/d/JNXDLeH63RzaCi)\n\nIn order to make local testing of your programs more convenient, the program calculating your results (checker) and the labyrinth visualizer will be available. This program is written in _python_3 programming language, that’s why you’re going to need _python_3 interpreter, as well as _pillow_ library, which you can install with the following command _pip3 install pillow_. _pip_3 is a utility program for _python_3 package (library) installation. It will be installed automatically with the _python_3 interpreter.\n\nExample command to run checker and visualizer: _python3 aimmaze.py maze.in robot.abc --image maze.png_. The checker can be run separately of visualization: _python3 aimmaze.py maze.in robot.abc_. Flag _\\--output-log_ will let you see the information of robots each step: _python3 aimmaze.py maze.in robot.abc --output-log_. Note _python_3 can be installed as _python_ on your computer.\n\nTo adjust image settings, you can edit constants at the beginning of the program _aimmaze_._py_.\n\n## Input\n\nThe first line contains integers _i_,  _W_,  _N_,  _M_,  _x_0,  _y_0,  _C_,  _D_,  _K_,  _E_.\n\n*   1 ≤ _i_ ≤ 14 – labyrinth’s number, which is needed for a checking program.\n*   1 ≤ _W_ ≤ 1018 – labyrinth’s weight, which is needed for a checking program.\n*   2 ≤ _N_, _M_ ≤ 1000 – labyrinth’s height and width.\n*   0 ≤ _x_0 ≤ _N_ - 1,  0 ≤ _y_0 ≤ _M_ - 1 – robot’s starting position (_x_0, _y_0).\n*   0 ≤ _C_ ≤ 2·_NM_ – number of walls.\n*   0 ≤ _D_ ≤ 105 – number of doors.\n*   0 ≤ _K_ ≤ 105 – number of keys.\n*   1 ≤ _E_ ≤ 1000 – number of exits.\n\nThe _x_ coordinate corresponds to the row number, _y_ – to the column number. (0, 0) cell is located on the left-up corner, so that _down_ direction increases the _x_ coordinate, while _right_ direction increases the _y_ coordinate.\n\nEach of the next _C_ lines contains 4 integers each _x_1, _y_1, _x_2, _y_2 – the coordinates of cells with a wall between them in a zero based indexing. It is guaranteed that |_x_1 - _x_2| + |_y_1 - _y_2| = 1,  0 ≤ _x_1, _x_2 ≤ _N_ - 1,  0 ≤ _y_1, _y_2 ≤ _M_ - 1. Also there are always walls around the labyrinth’s borders, which are not given in the labyrinths description.\n\nEach of the next _D_ lines contains door description in the same format as walls description. It is guaranteed that doors and walls don’t overlap.\n\nEach of the next _K_ rows contains a pair of integer which are the key coordinates in a zero based indexing.\n\nEach of the next _E_ rows contains a pair of integer which are the exit coordinates in a zero based indexing.\n\nIt is guaranteed that the robots starting position as well as keys and exits are located in pairwise different cells.\n\n## Output\n\nPrint a program in _abc_ language which passes the given labyrinth. Commands have to be separated by at least one space symbol. You can use arbitrary formatting for the program.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"你有一个机器人位于一个二维迷宫中，迷宫由 #cf_span[N × M] 个单元格组成。某些相邻的单元格之间由墙或门隔开。迷宫本身被周围的墙与外部隔开。一些迷宫单元格是出口。为了离开迷宫，机器人必须到达任意一个出口。某些单元格中包含钥匙。任何钥匙都可以打开任意一扇门，但门打开后钥匙会留在锁中。因此，每把钥匙只能使用一次。不存在同时包含钥匙和出口的单元格。此外，任意一对相邻单元格之间不会同时存在墙和门。\n\n你需要用 #cf_span[abc] 语言（见下方语言描述）编写一个程序，引导机器人到达某个出口。我们将迷宫的行从 #cf_span[0] 到 #cf_span[N - 1] 从上到下编号，列从 #cf_span[0] 到 #cf_span[M - 1] 从左到右编号。\n\n在 #cf_span[abc] 语言中，以下基本命令可用：\n\n此外，#cf_span[abc] 语言中还有以下控制命令：\n\n请注意，控制命令和基本命令可以任意嵌套。\n\n机器人将按顺序执行你的命令，直到它到达出口、命令用尽、执行了 #cf_span[terminate] 命令，或已执行的命令数量超过上限 #cf_span[5·106]。\n\n在 #cf_span[abc] 语言中，每个命令是一个独立的单词，命令之间必须用至少一个空格分隔。\n\n你需要编写一个程序，输出引导机器人走出迷宫的命令序列。当然，作为优秀的程序员，你应该优化这个序列。\n\n序列中非空格字符的总数不得超过 #cf_span[107]。如果你成功找到出口 #cf_span[i]，你将获得如下分数：\n\n如果你的序列未能使机器人到达出口，你将获得 #cf_span[0] 分。你的最终成绩是所有 #cf_span[Si] 的总和。你需要最大化这个总分。\n\n所有迷宫都将公开提供。你可以通过以下任意链接下载包含迷宫的压缩包，解压密码为 _aimtechiscool_：\n\n为方便本地测试你的程序，我们将提供计算你得分的检查程序（checker）和迷宫可视化工具。该程序使用 #cf_span[python3] 编写，因此你需要安装 #cf_span[python3] 解释器，以及 #cf_span[pillow] 库，可通过以下命令安装：_pip3 install pillow_。#cf_span[pip3] 是用于安装 #cf_span[python3] 包（库）的工具程序，它会随 #cf_span[python3] 解释器自动安装。\n\n运行检查程序和可视化工具的示例命令：_python3 aimmaze.py maze.in robot.abc --image maze.png_。检查程序可以独立于可视化运行：_python3 aimmaze.py maze.in robot.abc_。使用标志 _--output-log_ 可查看机器人每一步的信息：_python3 aimmaze.py maze.in robot.abc --output-log_。注意，在你的计算机上 #cf_span[python3] 可能被安装为 #cf_span[python]。\n\n你可以通过编辑程序 #cf_span[aimmaze.py] 开头的常量来调整图像设置。\n\n第一行包含整数 #cf_span[i,  W,  N,  M,  x0,  y0,  C,  D,  K,  E]。\n\n#cf_span[x] 坐标对应行号，#cf_span[y] 对应列号。#cf_span[(0, 0)] 单元格位于左上角，因此 #cf_span[down] 方向使 #cf_span[x] 坐标增加，而 #cf_span[right] 方向使 #cf_span[y] 坐标增加。\n\n接下来的 #cf_span[C] 行，每行包含 4 个整数 #cf_span[x1, y1, x2, y2] —— 以零索引表示两单元格之间墙的坐标。保证 #cf_span[|x1 - x2| + |y1 - y2| = 1,  0 ≤ x1, x2 ≤ N - 1,  0 ≤ y1, y2 ≤ M - 1]。此外，迷宫边界周围始终存在墙，但这些墙不会在迷宫描述中给出。\n\n接下来的 #cf_span[D] 行，每行以与墙相同的格式描述一扇门。保证门和墙不会重叠。\n\n接下来的 #cf_span[K] 行，每行包含一对整数，表示钥匙的零索引坐标。\n\n接下来的 #cf_span[E] 行，每行包含一对整数，表示出口的零索引坐标。\n\n保证机器人的起始位置、钥匙和出口均位于互不相同的单元格中。\n\n请输出一个用 #cf_span[abc] 语言编写的程序，以通过给定的迷宫。命令之间必须用至少一个空格分隔。你可以对程序使用任意格式。\n\n## Input\n\n第一行包含整数 #cf_span[i,  W,  N,  M,  x0,  y0,  C,  D,  K,  E]。   #cf_span[1 ≤ i ≤ 14] —— 迷宫编号，用于检查程序。  #cf_span[1 ≤ W ≤ 1018] —— 迷宫权重，用于检查程序。  #cf_span[2 ≤ N, M ≤ 1000] —— 迷宫的高度和宽度。  #cf_span[0 ≤ x0 ≤ N - 1,  0 ≤ y0 ≤ M - 1] —— 机器人的起始位置 #cf_span[(x0, y0)]。  #cf_span[0 ≤ C ≤ 2·NM] —— 墙的数量。  #cf_span[0 ≤ D ≤ 105] —— 门的数量。  #cf_span[0 ≤ K ≤ 105] —— 钥匙的数量。  #cf_span[1 ≤ E ≤ 1000] —— 出口的数量。#cf_span[x] 坐标对应行号，#cf_span[y] 对应列号。#cf_span[(0, 0)] 单元格位于左上角，因此 #cf_span[down] 方向使 #cf_span[x] 坐标增加，而 #cf_span[right] 方向使 #cf_span[y] 坐标增加。接下来的 #cf_span[C] 行，每行包含 4 个整数 #cf_span[x1, y1, x2, y2] —— 以零索引表示两单元格之间墙的坐标。保证 #cf_span[|x1 - x2| + |y1 - y2| = 1,  0 ≤ x1, x2 ≤ N - 1,  0 ≤ y1, y2 ≤ M - 1]。此外，迷宫边界周围始终存在墙，但这些墙不会在迷宫描述中给出。接下来的 #cf_span[D] 行，每行以与墙相同的格式描述一扇门。保证门和墙不会重叠。接下来的 #cf_span[K] 行，每行包含一对整数，表示钥匙的零索引坐标。接下来的 #cf_span[E] 行，每行包含一对整数，表示出口的零索引坐标。保证机器人的起始位置、钥匙和出口均位于互不相同的单元格中。\n\n## Output\n\n请输出一个用 #cf_span[abc] 语言编写的程序，以通过给定的迷宫。命令之间必须用至少一个空格分隔。你可以对程序使用任意格式。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ N, M \\in \\mathbb{Z}^+ $ denote the dimensions of the labyrinth grid.  \nLet $ (x_0, y_0) \\in \\{0, \\dots, N-1\\} \\times \\{0, \\dots, M-1\\} $ be the robot's starting position.  \nLet $ W \\subseteq \\{ ((x_1,y_1), (x_2,y_2)) \\mid |x_1 - x_2| + |y_1 - y_2| = 1 \\} $ be the set of walls between adjacent cells.  \nLet $ D \\subseteq \\{ ((x_1,y_1), (x_2,y_2)) \\mid |x_1 - x_2| + |y_1 - y_2| = 1 \\} \\setminus W $ be the set of doors between adjacent cells.  \nLet $ K \\subseteq \\{0, \\dots, N-1\\} \\times \\{0, \\dots, M-1\\} $ be the set of cells containing keys.  \nLet $ E \\subseteq \\{0, \\dots, N-1\\} \\times \\{0, \\dots, M-1\\} $ be the set of exit cells.  \nAssume $ K \\cap E = \\emptyset $, and no cell contains both a key and an exit.  \n\n**Constraints**  \n1. $ 1 \\leq N, M \\leq 100 $ (implied by typical contest bounds; exact bounds not specified but assumed bounded).  \n2. $ |W|, |D|, |K|, |E| $ are finite and given as input.  \n3. Robot may collect a key from a cell only once; each key opens exactly one door (any door, but only once).  \n4. Robot must reach any cell in $ E $ to exit.  \n5. Command sequence must not exceed $ 5 \\cdot 10^6 $ steps and $ 10^7 $ non-space characters.  \n\n**Objective**  \nFind a finite sequence of commands in the `abc` language (comprising `up`, `down`, `left`, `right`, `take`, `unlock`, `terminate`, and control structures `if`, `while`, `repeat`, etc.) such that:  \n- The robot, starting at $ (x_0, y_0) $, follows the sequence.  \n- The robot collects all necessary keys (from $ K $) to unlock required doors (in $ D $) along its path.  \n- The robot reaches any cell in $ E $.  \n- The sequence uses at most $ 10^7 $ non-space characters.  \n- Maximize the score $ S $, where $ S > 0 $ iff the robot exits; otherwise $ S = 0 $.  \n\n**Output**  \nA single string consisting of space-separated `abc` commands that satisfy the above.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF92101","tags":[],"sample_group":[["1 1 30 30 1 1 1 1 1 1\n1 1 1 2\n2 2 2 3\n1 4\n9 0","for-1111\n  take\n  open-up\n  open-left\n  open-right\n  open-down\n  move-left\n  if-ok\n    for-11\n      move-left\n  take\n  open-up\n  open-left\n  open-right\n  open-down\n    end\n  else\n    move-right\n    if-ok\n      for-11\n        move-right\n  take\n  open-up\n  open-left\n  open-right\n  open-down\n      end\n    else endif\n  endif\n\n  move-up\n  if-ok\n    for-11\n      move-up\n  take\n  open-up\n  open-left\n  open-right\n  open-down\n    end\n  else\n    move-down\n    if-ok\n      for-11\n        move-down\n  take\n  open-up\n  open-left\n  open-right\n  open-down\n      end\n    else endif\n  endif\n\nend"]],"created_at":"2026-03-03 11:00:39"}}