AT_ahc054_a [AHC054A] Treant's Forest

To the south of the Kingdom of AtCoder lies a mysterious forest commonly known as the "Lost Forest," where the paths change every time one enters. It is said that within this forest blooms a legendary flower called *Aura Amaryllis* (commonly abbreviated as AA), which brings happiness to those who find it. Even today, adventurers arrive in search of this flower. The true nature of the Lost Forest is that tree monsters known as "Treants" disguise themselves as trees to confuse adventurers. Treants sustain their lives by absorbing magical energy from lost adventurers, so they aim to keep the adventurers in the forest for as long as possible. However, if an adventurer fails to reach the AA, rumors will spread that "the flower never existed," and no one will enter the forest again. If that happens, the Treants will no longer be able to obtain magical energy and will eventually perish. Furthermore, adventurers explore the forest while mapping it to avoid getting lost. If a Treant moves to a location that has already been mapped, the adventurer will realize that it is not a real tree but a Treant in disguise and will cut it down. This situation must be avoided at all costs. As the boss of the Treants, your role is to adjust the placement of the Treants in response to the adventurer's movements to ensure that it takes longer for the adventurer to reach the AA.

There is a forest consisting of an $ N \times N $ grid of cells. The coordinates of the top-left cell are $ (0, 0) $ . The cell located $ i $ cells down and $ j $ cells to the right has coordinates $ (i, j) $ . Each cell is either an "empty cell" or a "tree". The area outside the $ N \times N $ grid is surrounded by trees. The cell $ (0, \lfloor \frac{N}{2} \rfloor) $ is the entrance to the forest and is an empty cell. The legendary flower blooms at cell $ (t_i, t_j) $ , which is also an empty cell. An adventurer has entered the forest in search of the legendary flower. The adventurer has three states: the **current position** and the **revealed cells**, which are public information, and the **destination**, which is hidden. A map of the forest assuming all unrevealed cells are empty is called the **tentative map**. Initially, the **current position** is the forest entrance, the **revealed cells** include only that one cell and all cells outside the $ N \times N $ grid, and the **destination** is unset. Each turn, the adventurer's actions are processed in the following order: 1. If the legendary flower is at the **current position**, the goal is achieved and the adventurer stops moving. 2. For each of the four directions (up, down, left, right), add to the **revealed cells** all unrevealed cells from the **current position** up to and including the first "tree" cell encountered in that direction. 3. If the legendary flower is included in the **revealed cells**, set the **destination** to that cell. 4. If the **destination** is set but is unreachable from the current position in the **tentative map** using only empty cells, unset the **destination**. 5. If the **destination** is unset or is a cell in the **revealed cells** other than the legendary flower, choose one cell uniformly at random from the unrevealed cells that are reachable from the current position via empty cells in the **tentative map**, and set it as the **destination** (if no such cell exists, this will result in a WA, as described below). 6. In the **tentative map**, compute the shortest distance to the **destination** using only empty cells. Move to an adjacent empty cell that shortens the distance to the **destination**. If multiple such cells exist, choose the one in the order of preference: up, down, left, right. As the boss of the tree monsters known as "Treants," your goal is to direct the Treants to confuse the adventurer and maximize the number of turns it takes to reach the legendary flower. At the beginning of each turn, you may choose any number of empty cells that are not part of the **revealed cells** and place one Treant in each. Cells where Treants are placed are no longer considered "empty" and are treated as "trees" from that point onward. Treants cannot be moved once placed. You must ensure that there is always at least one path from the forest entrance to the legendary flower consisting only of empty cells. If no such path exists, your solution will result in a WA. ### Input & Output Format At the beginning, the following information is given via Standard Input: > $ N $ $ t_i $ $ t_j $ $ b_{0,0}\cdots b_{0,N-1} $ $ \vdots $ $ b_{N-1,0}\cdots b_{N-1,N-1} $ - $ N $ is the width and height of the forest and satisfies $ 20 \leq N \leq 40 $ . - $ (t_i, t_j) $ is the coordinate of the legendary flower and satisfies $ 0 \leq t_i, t_j \leq N - 1 $ , with a guaranteed Manhattan distance of at least 5 from the forest entrance $ (0, \lfloor \frac{N}{2} \rfloor) $ . - $ b_{i,0} \cdots b_{i,N-1} $ is a string of length $ N $ , where the $ j $ -th character $ b_{i,j} $ is `.` if cell $ (i, j) $ is an empty cell, and `T` if it is a tree. - It is guaranteed that every empty cell is reachable from the forest entrance $ (0, \lfloor \frac{N}{2} \rfloor) $ by traversing only through empty cells. Next, repeat the following process. At the beginning of each turn, the adventurer's current position and the cells newly revealed in the previous turn are given via Standard Input in the following format: > $ p_i $ $ p_j $ $ n $ $ x_0 $ $ y_0 $ $ \cdots $ $ x_{n-1} $ $ y_{n-1} $ - $ (p_i, p_j) $ is the adventurer's current position. - $ n $ is the number of cells that were newly revealed in the previous turn, and $ (x_k, y_k) $ represents the coordinates of the $ k $ -th such cell. - On the first turn, $ (p_i, p_j) = (0, \lfloor \frac{N}{2} \rfloor) $ , $ n = 1 $ , and $ (x_0, y_0) = (0, \lfloor \frac{N}{2} \rfloor) $ . If $ (p_i, p_j) = (t_i, t_j) $ , it means the adventurer has reached the legendary flower. In that case, terminate the loop and end the program. Otherwise, let $ (x_0', y_0'), \cdots, (x_{m-1}', y_{m-1}') $ be the set of cells where Treants will be placed before the start of this turn, and output the following format to Standard Output: > $ m $ $ x_0' $ $ y_0' $ $ \cdots $ $ x_{m-1}' $ $ y_{m-1}' $ **The output must be followed by a new line, and you have to flush Standard Output.** Otherwise, the submission might be judged as TLE. **(2025/9/21 06:00 UTC Update)** The execution time limit includes not only the contestant's solution program but also the judge-side tester program. In this problem setting, it is difficult for the solution program to terminate at an arbitrary timing, so the following cutoff output specification has been added to make it easier to avoid TLE. **Cutoff Output**: Instead of outputting the set of cells where new Treants are placed in the above format, the program may output a line containing only `-1` and then terminate immediately. In that case, the subsequent turns will be treated as if the output had been $ m=0 $ until the adventurer finds the legendary flower, and the execution time spent by the tester on that processing will not be counted toward the time limit. [Show example](https://img.atcoder.jp/ahc054/YDAxDRZr_v2.html?lang=en&seed=0&output=sample)

N/A

N/A

### Scoring The number of moves the adventurer takes to reach the legendary flower from the forest entrance is the absolute score for that test case. The higher the absolute score, the better. For each test case, we compute the **relative score** $ \mathrm{round}(10^9\times \frac{\mathrm{YOUR}}{\mathrm{MAX}}) $ , where YOUR is your absolute score and MAX is the highest absolute score among all competitors obtained on that test case. The score of the submission is the sum of the relative scores. The 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 MAX calculation for those test cases. The 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. #### Number of test cases - Provisional test: 100 - System test: 3000. We will publish [seeds.txt](https://img.atcoder.jp/ahc054/seeds.txt) (sha256=f46e04db0ec8f80d641bbc8e166b1d2f4050a340b356acea1adce1a41a0a7fc8) after the contest is over. #### About relative evaluation system In 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 MAX for each test case when calculating the relative scores. The 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. #### About execution time Execution 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. ### Input Generation Let $ \mathrm{rand}(L, U) $ be a function that generates a uniformly random integer between $ L $ and $ U $ , inclusive. Generate the forest size $ N $ by $ N = \mathrm{rand}(20, 40) $ . Start with all cells as empty, and generate the tree placement using the following procedure: First, determine the maximum number of trees $ K $ by $ K = \max(1, \mathrm{rand}(0, \lfloor N^2 / 6 \rfloor)) $ . List the $ N^2 - 1 $ cells excluding the forest entrance in a random order as $ (i_0, j_0), \cdots, (i_{N^2 - 2}, j_{N^2 - 2}) $ , and for each $ k $ , perform the following: Tentatively place a tree at $ (i_k, j_k) $ and check whether all empty cells are still reachable from the forest entrance. If they are not, cancel the placement. Stop the process once the number of placed trees reaches $ K $ . Finally, choose the coordinates of the legendary flower $ (t_i, t_j) $ uniformly at random from the empty cells that satisfy the required conditions. ### Tools (Input generator, local tester, and visualizer) - [Web version](https://img.atcoder.jp/ahc054/YDAxDRZr_v2.html?lang=en): This is more powerful than the local version providing animations. - [Local version](https://img.atcoder.jp/ahc054/YDAxDRZr_v2.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/ahc054/YDAxDRZr_v2_windows.zip): If you are not familiar with the Rust language environment, please use this instead. Please be aware that sharing visualization results or discussing solutions/ideas during the contest is prohibited. #### Input File Format Used by the Tool The input file used for the local tester follows the format below: > $ N $ $ t_i $ $ t_j $ $ b_{0,0}\cdots b_{0,N-1} $ $ \vdots $ $ b_{N-1,0}\cdots b_{N-1,N-1} $ $ q_i^0 $ $ q_j^0 $ $ \vdots $ $ q_i^{N^2-2} $ $ q_j^{N^2-2} $ The entries $ (q_i^k, q_j^k) $ appended at the end represent the $ k $ -th destination candidates. When the adventurer chooses a destination, the list is traversed in this order, and the first cell that satisfies the conditions is selected. The list $ q $ is generated by shuffling the $ N^2 - 1 $ cells excluding the forest entrance in a random order. ### Sample Solution (Python) A sample solution in Python is shown below. This program keeps track of the revealed cells but does not place any Treants. ``` N, ti, tj = map(int, input().split()) b = [input() for _ in range(N)] revealed = [[False] * N for _ in range(N)] while True: pi, pj = map(int, input().split()) parts = input().split() n = int(parts[0]) xy = list(map(int, parts[1:])) for k in range(n): x = xy[2 * k] y = xy[2 * k + 1] revealed[x][y] = True if pi == ti and pj == tj: break print(0, flush=True) ```