AT_ahc067_a [AHC067A] Castle Renovation with Linked Doors

Demon King Takahashi has received word that the hero Aoki is approaching his castle. To buy as much time as possible before the hero reaches the throne, the Demon King has decided to renovate the castle by installing linked doors and switches. However, since the Demon King's army has been infiltrated by a spy working for the hero, the renovation plan is completely known to him. Moreover, the hero is extremely clever, and if the throne is reachable, he will reach it using as few actions as possible. As one of the Demon King's most capable subordinates, you are asked to devise a renovation plan that still delays the hero for as long as possible. 

There is a Demon King's castle consisting of $ N\times N $ cells. Let $ (0,0) $ be the coordinates of the top-left cell, and let $ (i,j) $ denote the cell that is $ i $ cells downward and $ j $ cells to the right from there. Each cell is either an empty cell `.` or an obstacle `#`. All cells outside the $ N\times N $ grid are regarded as obstacles. Cell $ (0,0) $ contains the entrance, and cell $ (N-1,N-1) $ contains the throne. Both of these cells are empty cells. Before the hero enters the castle, you may install **doors** and **switches** inside the castle. #### Doors There are $ 2K $ **types** of doors, numbered $ 0,1,\ldots,2K-1 $ . Hereafter, a door of type $ g $ will simply be called **door $ g $** . A door can be installed between two orthogonally adjacent cells, and at most $ M $ doors may be installed in total. At most one door can be installed between the same two cells. Multiple doors of the same type may be installed. #### Switches There are $ K $ **kinds** of switches, numbered $ 0,1,\ldots,K-1 $ . Hereafter, a switch of kind $ k $ will simply be called **switch $ k $** . At most one switch can be installed in each cell. Multiple switches of the same kind may be installed in different cells. There may also be kinds of switches that are not installed at all. Switches may also be installed at the entrance $ (0,0) $ and the throne $ (N-1,N-1) $ . #### Linkage Between Doors and Switches For each $ k=0,1,\ldots,K-1 $ , door $ 2k $ and door $ 2k+1 $ are controlled by switch $ k $ . All doors of the same type share the same open/closed state. Initially, door $ 2k $ is open, and door $ 2k+1 $ is closed. Each time switch $ k $ is pressed, the open/closed states of door $ 2k $ and door $ 2k+1 $ are swapped. That is, when switch $ k $ has been pressed an even number of times, door $ 2k $ is open and door $ 2k+1 $ is closed. When switch $ k $ has been pressed an odd number of times, door $ 2k $ is closed and door $ 2k+1 $ is open. A door may be installed between a cell and an obstacle cell, but movement through such a door is impossible. A switch may be installed on an obstacle cell, but such a switch cannot be pressed. #### Hero's Actions After the renovation of the castle is complete, the hero enters from the entrance $ (0,0) $ . On each turn, the hero may choose and perform one of the following two actions. 1. Move to an orthogonally adjacent empty cell. However, if there is a door between the current cell and the destination cell and that door is closed, the hero cannot move in that direction. 2. If there is a switch on the current cell, press that switch. Even if there is a switch on the current cell, the hero does not necessarily have to press it. The hero may move to an adjacent cell without pressing the switch. The hero knows the entire placement of the doors and switches you installed. If the throne is reachable, the hero reaches the throne using as few actions as possible. Your objective is to maximize the minimum number of actions required for the hero to reach the throne from the entrance. #### Supplement: Minimum Number of Actions for the Hero For a given output renovation plan, the minimum number of actions $ T $ can be computed by performing a breadth-first search whose state consists of the current position and, for each switch $ k $ , the parity of the number of times switch $ k $ has been pressed. There are at most $ N^2 $ possible current positions, and the states of the switches can be represented by $ K $ bits, giving $ 2^K $ possibilities. Therefore, $ T $ can be computed in $ O(2^K N^2) $ time. The following is an example implementation in python for computing the minimum number of actions. ``` from collections import deque def calc_T(N, K, c, door_h, door_v, switch): """ N: board size K: number of switch kinds c: map. c[i][j] is either '.' or '#' door_h: doors in the vertical direction. door_h[i][j] is the type of the door between (i,j) and (i+1,j). -1 if there is no door door_v: doors in the horizontal direction. door_v[i][j] is the type of the door between (i,j) and (i,j+1). -1 if there is no door switch: switch[i][j] is the kind of the switch placed on cell (i,j). -1 if there is no switch Returns: The minimum number of actions required to reach the throne (N-1,N-1) from the entrance (0,0). Returns 0 if it is unreachable. """ def is_open(g, mask): """Returns whether the door of type g is open in state mask.""" if g == -1: return True k = g // 2 return ((mask >> k) & 1) == (g & 1) dist = [[[-1] * N for _ in range(N)] for _ in range(1

Input is given from Standard Input in the following format. > $ N $ $ M $ $ K $ $ c_0 $ $ \vdots $ $ c_{N-1} $ - In all test cases, the board size $ N $ is fixed to $ 20 $ . - In all test cases, the maximum number of doors that can be installed, $ M $ , is fixed to $ 50 $ . - In all test cases, the number of switch kinds, $ K $ , is fixed to $ 10 $ . - $ c_i $ is a string of length $ N $ , and its $ j $ -th character $ c_{i,j} $ is `.` if cell $ (i,j) $ is an empty cell and `#` if it is an obstacle. - $ c_{0,0}=c_{N-1,N-1}= $ `.`. - It is guaranteed that every empty cell is reachable from the entrance $ (0,0) $ by passing only through empty cells.

First, let $ D $ be the number of doors to install, and output the placement of the doors to Standard Output in the following format. > $ D $ $ d_0 $ $ i_0 $ $ j_0 $ $ g_0 $ $ \vdots $ $ d_{D-1} $ $ i_{D-1} $ $ j_{D-1} $ $ g_{D-1} $ The $ a $ -th door is represented by its direction $ d_a $ , coordinates $ (i_a,j_a) $ , and door type $ g_a $ . - If $ d_a=0 $ , install door $ g_a $ between cell $ (i_a,j_a) $ and cell $ (i_a+1,j_a) $ . - If $ d_a=1 $ , install door $ g_a $ between cell $ (i_a,j_a) $ and cell $ (i_a,j_a+1) $ . The output must satisfy the following conditions. - $ 0\leq D\leq M $ - For each door, $ d_a $ is either 0 or 1. - For each door, $ 0\leq g_a

### Scoring For the renovation plan you output, if the hero can reach the throne $ (N-1,N-1) $ from the entrance $ (0,0) $ in a finite number of actions, let $ T $ be the minimum number of actions required to do so. In this case, you will obtain the following score. \\\[ \\mathrm{round}\\left(10^6\\times \\log\_2 \\frac{T}{N}\\right) \\\] If the hero cannot reach the throne, the score will be $ 1 $ . There are $ 150 $ test cases, and the score of a submission is the total score for each test case. If your submission produces an illegal output or exceeds the time limit for some test cases, the submission itself will be judged as WA or TLE , and the score of the submission will be zero. The highest score obtained during the contest will determine the final ranking, and there will be no system test after the contest. If more than one participant gets the same score, they will be ranked in the same place regardless of the submission time. ### Input Generation $ N=20 $ , $ M=50 $ , and $ K=10 $ are fixed. First, start with all cells being empty cells. Arrange the $ N^2-2 $ cells other than $ (0,0) $ and $ (N-1,N-1) $ in random order, and process them in that order as follows. > Let the target cell be $ (i,j) $ . If at least 3 of the 4 orthogonally adjacent cells of cell $ (i,j) $ are obstacle cells, skip the process for this cell. Cells outside the $ N\times N $ grid are counted as obstacles. Otherwise, temporarily change cell $ (i,j) $ into an obstacle. If this change makes all empty cells disconnected, change cell $ (i,j) $ back into an empty cell. Otherwise, leave cell $ (i,j) $ as an obstacle. Next, arrange all obstacle cells in random order, and process them in that order as follows. > Let the target cell be $ (i,j) $ . If at least one of the 4 orthogonally adjacent cells of cell $ (i,j) $ is an empty cell, change cell $ (i,j) $ into an empty cell. Once the number of times an obstacle cell has been changed into an empty cell reaches $ N $ , terminate this process. ### Tools (Input generator and visualizer) - [Web version](https://img.atcoder.jp/ahc067/BpPfrS30.html?lang=en): This is more powerful than the local version providing animations. - [Local version](https://img.atcoder.jp/ahc067/BpPfrS30.zip): You need a compilation environment of [Rust language](https://www.rust-lang.org/). - [Pre-compiled binary for Windows](https://img.atcoder.jp/ahc067/BpPfrS30_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.