{"problem":{"name":"Group Commands and Wall Planning","description":{"content":"There is an $N \\times N$ grid. The coordinate of the top-left cell is $(0, 0)$, and the coordinate of the cell $i$ rows down and $j$ columns to the right is $(i, j)$. There are walls between some adja","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"awtf2025heuristic_a"},"statements":[{"statement_type":"Markdown","content":"There is an $N \\times N$ grid. The coordinate of the top-left cell is $(0, 0)$, and the coordinate of the cell $i$ rows down and $j$ columns to the right is $(i, j)$. There are walls between some adjacent cells.\nThere are $K$ robots on the grid. The initial position of the $k$\\-th robot is $(i_k, j_k)$, and its destination is $(i_k', j_k')$. Takahashi wants to operate these robots to bring all of them to their respective destinations.\nBefore making any moves, the following two types of preparations can be made:\n\n1.  In addition to the existing walls, you may add walls between any adjacent cells.\n2.  Divide the robots into groups. Each robot belongs to exactly one group, and all robots in the same group can be operated simultaneously.\n\nThese preparations must be completed before the first move. After that, no additional walls can be placed and the group assignments cannot be changed.\nNext, the robots can be moved by repeatedly performing the following two types of operations:\n\n1.  **Group Command**: Specify a group and a direction (up, down, left, or right). All robots in that group will attempt to move one cell in the specified direction. If there is a wall between the current and target cells, or if another robot is occupying the target cell, the robot does not move. Among the robots belonging to the group, those farthest in the direction of movement will attempt to move first. For example, if robots are at $(1, 0)$ and $(2, 0)$ and the direction is up, the robot at $(1, 0)$ will move to $(0, 0)$ first (since it has a smaller $i$ coordinate), and then the robot at $(2, 0)$ will move to the now-empty $(1, 0)$.\n    \n2.  **Individual Command**: Specify a robot and a direction (up, down, left, or right). The specified robot will attempt to move one cell in the specified direction. If there is a wall between the current and target cells, or if another robot is occupying the target cell, the robot does not move.\n    \n\nEven if a robot reaches its destination once, if it moves away from the destination due to subsequent operations, it is not considered to have reached its destination.\nYou may perform at most $K N^2$ operations. Guide all robots to their destinations using as few operations as possible.\n\n## Input\n\nInput is given from Standard Input in the following format.\n\n$N$ $K$\n$i_0$ $j_0$ $i_0'$ $j_0'$\n$\\vdots$\n$i_{K-1}$ $j_{K-1}$ $i_{K-1}'$ $j_{K-1}'$\n$v_{0,0} \\cdots v_{0,N-2}$\n$\\vdots$\n$v_{N-1,0} \\cdots v_{N-1,N-2}$\n$h_{0,0} \\cdots h_{0,N-1}$\n$\\vdots$\n$h_{N-2,0} \\cdots h_{N-2,N-1}$\n\n*   In all test cases, $N=30$ is fixed.\n*   $10 \\leq K \\leq 100$\n*   $(i_k, j_k)$ represents the initial position of the $k$\\-th robot.\n*   $(i_k', j_k')$ represents the destination of the $k$\\-th robot.\n*   All initial positions and all destinations are each mutually distinct, but the initial position of robot $k$ may coincide with the destination of robot $k'$.\n*   Each $v_{i,0} \\cdots v_{i,N-2}$ is a binary string of length $N-1$. The $j$\\-th character $v_{i,j}$ indicates whether there is a wall (`1`) or not (`0`) between cells $(i, j)$ and $(i, j+1)$.\n*   Each $h_{i,0} \\cdots h_{i,N-1}$ is a binary string of length $N$. The $j$\\-th character $h_{i,j}$ indicates whether there is a wall (`1`) or not (`0`) between cells $(i, j)$ and $(i+1, j)$.\n*   It is guaranteed that all cells are mutually reachable.\n\n## Scoring\n\nLet $T$ be the number of operations performed, and let $d_k$ be the Manhattan distance between the final position and the destination of robot $k$. Then, you obtain the following absolute score: \\\\\\[ T + 100 \\\\times \\\\sum_k d_k \\\\\\]\n**The lower the absolute score, the better.**\nFor each test case, we compute the **relative score** $\\mathrm{round}(10^9\\times \\frac{\\mathrm{MIN}}{\\mathrm{YOUR}})$, where YOUR is your absolute score and MIN is the lowest absolute score among all competitors obtained on that test case. The score of the submission is the sum of the relative scores.\nThe final ranking will be determined by the system test with more inputs which will be run after the contest is over. In both the provisional/system test, if your submission produces illegal output or exceeds the time limit for some test cases, only the score for those test cases will be zero, and your submission will be excluded from the MIN calculation for those test cases.\nThe system test will be performed only for **the last submission which received a result other than CE** . Be careful not to make a mistake in the final submission.\n\n#### Number of test cases\n\n*   Provisional test: 50\n*   System test: 2000. We will publish [seeds.txt](https://img.atcoder.jp/awtf2025heuristic/seeds.txt) (sha256=063a84b1c0dc9388b0996eed0bc645529c931c139bee6b8e0e84a4faf3e06c40) after the contest is over.\n\n#### About relative evaluation system\n\nIn both the provisional/system test, the standings will be calculated using only the last submission which received a result other than CE. Only the last submissions are used to calculate the MIN for each test case when calculating the relative scores.\nThe scores shown in the standings are relative, and whenever a new submission arrives, all relative scores are recalculated. On the other hand, the score for each submission shown on the submissions page is the sum of the absolute score for each test case, and the relative scores are not shown. In order to know the relative score of submission other than the latest one in the current standings, you need to resubmit it. If your submission produces illegal output or exceeds the time limit for some test cases, the score shown on the submissions page will be 0, but the standings show the sum of the relative scores for the test cases that were answered correctly.\n\n#### About execution time\n\nExecution time may vary slightly from run to run. In addition, since system tests simultaneously perform a large number of executions, it has been observed that execution time increases by several percent compared to provisional tests. For these reasons, submissions that are very close to the time limit may result in TLE in the system test. Please measure the execution time in your program to terminate the process, or have enough margin in the execution time.\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"awtf2025heuristic_a","tags":[],"sample_group":[["30 59\n8 18 11 17\n8 23 17 15\n1 12 11 7\n19 17 24 22\n23 9 8 20\n21 17 26 10\n4 19 12 29\n19 29 7 7\n19 24 12 19\n24 26 19 10\n12 23 4 18\n8 22 26 11\n23 18 16 26\n28 14 8 14\n6 12 21 12\n28 18 13 21\n21 28 17 3\n5 14 11 20\n28 13 19 28\n27 18 18 8\n7 21 28 23\n25 13 0 17\n15 17 4 24\n15 19 7 0\n3 26 10 25\n26 20 7 6\n17 10 28 17\n8 9 5 21\n2 26 12 9\n18 29 21 10\n7 20 10 24\n23 5 11 18\n24 12 4 9\n9 19 26 13\n1 0 15 12\n9 8 3 8\n29 9 15 24\n22 14 3 18\n15 16 15 1\n1 29 19 4\n9 12 27 21\n2 23 9 4\n18 24 14 18\n22 7 8 1\n20 29 24 3\n3 2 12 17\n10 11 15 20\n16 6 24 0\n6 5 29 17\n29 20 26 16\n14 18 0 9\n29 11 26 20\n24 22 1 13\n1 5 15 9\n26 10 27 26\n20 20 2 6\n6 28 15 2\n22 6 0 0\n6 17 16 13\n00000000000000000000000000000\n00000000000000000000000000000\n00000000000000000000000000000\n00000000000000000000000000000\n00000000000000000000000000000\n00000000000000000000000000000\n00000000000000000000000000000\n00000000000000000000000000000\n00000000000000000000000000000\n00000000000000000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000000000000000000000\n00000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000","00000000000000000000000000000\n01000000000000000000000000000\n00000000000000000000000000000\n00000000000000000000001000000\n00000000000100000000000000000\n00000000000000000000000000001\n00000000000000000000000000000\n00000000000000000000000000000\n00000000000000000000000000000\n00000000000000000000000000000\n00000000000100000000000000000\n00000000000100000000010000000\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000100001000000000000\n00000000000100000000000100000\n00000000000100000000000001000\n00010000000100000000000000000\n00000000000100000000000000000\n00000010000100000000000000000\n01000000000100000000000000000\n00000000000100000000000000100\n00000000000100000000000000000\n00000001000100000000000000000\n00000000000100000000000000000\n00000000000100000000000001010\n00000000000100000000000000000\n00000000000100000000000000000\n00000000000000000000000000000\n00000000000000000000000000000\n000000100000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000100000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000001000000\n000000000000000000000000000000\n000000000000000000000000000100\n000001000000000000000000000000\n000000000000000000000100100000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000010000000000000\n000000000000000000000000100000\n000000000000000000000000000000\n000000000000000000000000000000\n000000000000000000000000010000\n000000100000000000000000000000\n000000000000000000000000000000\n000000000000000010000000000000\n000000000000000100000000000000\n000000000000000000000000000000\n000000000000000000000000000000\n000000001000000000000000000000\n6 2 3 3 8 9 0 1 8 0 9 7 5 6 3 6 7 5 4 6 7 3 0 1 5 8 3 4 5 6 7 0 0 3 9 5 4 6 2 8 8 6 6 0 9 7 2 1 3 9 3 6 2 6 5 4 0 3 8\ni 16 D\ng 0 U\ni 27 U\ng 1 L\ni 0 D\ng 5 D\ni 58 D\ni 52 U\ni 44 D\ni 17 D\ng 0 U\ng 4 U\ni 32 U\ng 2 U\ni 31 U\ng 9 L\ng 0 U\ng 2 L\ni 30 D\ng 3 D\ni 48 D\ng 2 L\ni 14 D\ni 1 D\ng 7 D\ng 3 D\ni 14 D\ng 1 L\ni 32 U\ni 57 U\ni 56 D\ni 21 U\ng 6 D\ni 4 U\ni 20 D\ng 7 D\ni 7 U\ni 39 D\ni 42 U\ng 7 D\ni 15 U\ni 32 U\ni 6 D\ng 6 D\ni 50 U\ng 5 D\ng 4 U\ng 2 L\ni 40 D\ng 2 L\ni 29 D\ni 1 D\ng 7 D\ng 7 D\ni 41 D\ng 9 L\ni 48 D\ni 16 D\ng 8 L\ng 5 D\ng 6 D\ni 14 D\ni 50 L\ng 6 U\ni 29 D\ni 46 R\ng 6 L\ni 9 D\ng 6 D\ni 16 L\ni 7 U\ni 2 D\ng 9 D\ng 5 D\ng 8 L\ng 8 L\ni 4 R\ni 40 D\ni 10 U\ng 4 R\ni 50 L\ng 9 L\ni 28 L\ni 32 U\ng 3 D\ni 4 U\ni 6 D\ni 35 U\ni 33 D\ng 0 U\ng 7 R\ni 23 U\ng 4 R\ng 6 D\ni 7 U\ni 57 U\ng 0 U\ng 5 D\ng 6 D\ng 3 D"]],"created_at":"2026-03-03 11:01:14"}}