Smoothing by Swaps

There is an $N\times N$ square board. Let $(0, 0)$ be the coordinates of the top-left square, and $(i, j)$ be the coordinates of the square located $i$ squares down and $j$ squares to the right from there. The perimeter of the $N\times N$ board is surrounded by walls, and there may also be walls between squares. Two squares that share an edge are defined as "adjacent squares" when there is no wall between them. (added at 13:15 JST) Each square $(i,j)$ has a unique number $a_{(i,j)}$ from $1$ to $N^2$. Starting from their favorite initial position on the grid, Takahashi and Aoki perform the following sequence of actions at most $4 N^2$ steps. 1. The numbers on Takahashi's and Aoki's current positions can be exchanged if they want to. 2. Takahashi can move to a square adjacent to his current position if he wants to. 3. Aoki can move to a square adjacent to his current position if he wants to. The sequence of actions is performed in the order $1\rightarrow 2\rightarrow 3$, and the entire sequence is considered as a single step. They may move to adjacent squares without exchanging numbers, or they may stay in the same square after exchanging numbers. It is also acceptable that their current positions are in the same square. Please determine their actions so that the final numbers between adjacent squares are as close as possible. ## Input Input is given from Standard Input in the following format. $t$ $N$ $v_{0,0} \cdots v_{0,N-2}$ $\vdots$ $v_{N-1,0} \cdots v_{N-1,N-2}$ $h_{0,0}\cdots h_{0,N-1}$ $\vdots$ $h_{N-2,0} \cdots h_{N-2,N-1}$ $a_{0,0}$ $\cdots$ $a_{0,N-1}$ $\vdots$ $a_{N-1,0}$ $\cdots$ $a_{N-1,N-1}$ * $t$ is an integer representing the input generation method, satisfying $0\leq t\leq 19$. See the Input Generation section for details. * $N$ is the horizontal and vertical size of the board and satisfies $10\leq N\leq 100$. * $v_{i,0}\cdots v_{i,N-2}$ is a string of length $N-1$ consisting of only `0` and `1`. $v_{i,j}=1$ if and only if there is a wall between square $(i,j)$ and its right neighbor $(i,j+1)$. * $h_{i,0}\cdots h_{i,N-1}$ is a string of length $N$ consisting of only `0` and `1`. $h_{i,j}=1$ if and only if there is a wall between square $(i,j)$ and its lower neighbor $(i+1,j)$. * All squares are guaranteed to be reachable each other. * $a_{i,j}$ denotes the number initially written in the square $(i,j)$, and satisfies $1\leq a_{i,j}\leq N^2$. ## Scoring Let $E$ be the set of whole pairs of adjacent squares, and consider the sum of squares of the differences of numbers in adjacent squares $\sum_{u,v\in E}(a_u-a_v)^2$. Let $D'$ be the sum of squares in the initial state and $D$ be the sum of squares in the final state. Then, you will obtain the following score. \\\[ \\max\\left(1, \\mathrm{round}\\left(10^6\\times \\log_2\\frac{D'}{D}\\right)\\right) \\\] There are 200 test cases in total, $10$ for each $t$ value described below, and the sum of the scores for each test case is the score for the submission. The test cases are separated into distinct test sets (`test_t`) for each $t$ value, and in case of incorrect output or exceeding the time limit, only the corresponding test set will be scored $0$. 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. [samples]