Story

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.

Problem Statement

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 << K)]
    dist[0][0][0] = 0

    que = deque()
    que.append((0, 0, 0))

    while que:
        mask, i, j = que.popleft()
        d = dist[mask][i][j]

        if (i, j) == (N - 1, N - 1):
            return d

        # Action 1: Move to an adjacent empty cell
        for di, dj in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            ni, nj = i + di, j + dj

            if not (0 <= ni < N and 0 <= nj < N):
                continue
            if c[ni][nj] == '#':
                continue

            if di == 1:
                g = door_h[i][j]
            elif di == -1:
                g = door_h[ni][nj]
            elif dj == 1:
                g = door_v[i][j]
            else:
                g = door_v[ni][nj]

            if not is_open(g, mask):
                continue

            if dist[mask][ni][nj] == -1:
                dist[mask][ni][nj] = d + 1
                que.append((mask, ni, nj))

        # Action 2: Press the switch on the current cell
        s = switch[i][j]
        if s != -1:
            nmask = mask ^ (1 << s)
            if dist[nmask][i][j] == -1:
                dist[nmask][i][j] = d + 1
                que.append((nmask, i, j))

    return 0

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.