Problem:


Problem J: Infected Land

The earth is under an attack of a deadly virus. Luckily, prompt actions of the Ministry of
Health against this emergency successfully confined the spread of the infection within a square
grid of areas. Recently, public health specialists found an interesting pattern with regard to the
transition of infected areas. At each step in time, every area in the grid changes its infection
state according to infection states of its directly (horizontally, vertically, and diagonally) adjacent
areas.

    
 An infected area continues to be infected if it has two or three adjacent infected areas.

    
 An uninfected area becomes infected if it has exactly three adjacent infected areas.

    
 An area becomes free of the virus, otherwise.

Your mission is to fight against the virus and disinfect all the areas. The Ministry of Health
lets an anti-virus vehicle prototype under your command. The functionality of the vehicle is
summarized as follows.

    
 At the beginning of each time step, you move the vehicle to one of the eight adjacent areas.
      The vehicle is not allowed to move to an infected area (to protect its operators from the
      virus). It is not allowed to stay in the same area.

    
 Following vehicle motion, all the areas, except for the area where the vehicle is in, change
      their infection states according to the transition rules described above.

      Special functionality of the vehicle protects its area from virus infection even if the area
      is adjacent to exactly three infected areas. Unfortunately, this virus-protection capability
      of the vehicle does not last. Once the vehicle leaves the area, depending on the infection
      states of the adjacent areas, the area can be infected.

      The area where the vehicle is in, which is uninfected, has the same effect to its adjacent
      areas as an infected area as far as the transition rules are concerned.

The following series of figures illustrate a sample scenario that successfully achieves the goal.

Initially, your vehicle denoted by @ is found at (1, 5) in a 5 &times; 5-grid of areas, and you see some
infected areas which are denoted by #'s.

Firstly, at the beginning of time step 1, you move your vehicle diagonally to the southwest,
that is, to the area (2, 4). Note that this vehicle motion was possible because this area was not
infected at the start of time step 1.

Following this vehicle motion, infection state of each area changes according to the transition
rules. The column "1-end" of the figure illustrates the result of such changes at the end of time
step 1. Note that the area (3, 3) becomes infected because there were two adjacent infected areas
and the vehicle was also in an adjacent area, three areas in total.

In time step 2, you move your vehicle to the west and position it at (2, 3).

Then infection states of other areas change. Note that even if your vehicle had exactly three
infected adjacent areas (west, southwest, and south), the area that is being visited by the vehicle
is not infected. The result of such changes at the end of time step 2 is as depicted in "2-end".

Finally, in time step 3, you move your vehicle to the east. After the change of the infection
states, you see that all the areas have become virus free! This completely disinfected situation
is the goal. In the scenario we have seen, you have successfully disinfected all the areas in three
time steps by commanding the vehicle to move (1) southwest, (2) west, and (3) east.

Your mission is to find the length of the shortest sequence(s) of vehicle motion commands that
can successfully disinfect all the areas.

Input

The input is a sequence of datasets. The end of the input is indicated by a line containing a
single zero. Each dataset is formatted as follows.

        n

       a11   a12 ...   a1n

       a21   a22 ...   a2n

...

       an1   an2 ...   ann

Here, n is the size of the grid. That means that the grid is comprised of n &times; n areas. You
may assume 1 ≤ n ≤ 5. The rest of the dataset consists of n lines of n letters. Each letter aij
specifies the state of the area at the beginning: '#' for infection, '.' for free of virus, and '@' for
the initial location of the vehicle. The only character that can appear in a line is '#', '.', or '@'.
Among n &times; n areas, there exists exactly one area which has '@'.

Output

For each dataset, output the minimum number of time steps that is required to disinfect all the
areas. If there exists no motion command sequence that leads to complete disinfection, output
-1. The output should not contain any other extra character.

Sample Input

3
...
.@.
...
3
.##
.#.
@##
3
##.
#..
@..
5
....@
##...
#....
...#.
##.##
5
#...#
...#.
#....
...##
..@..
5
#....
.....
.....
.....
..@..
5
#..#.
#.#.#
.#.#.
....#
.#@##
5
..##.
..#..
#....
#....
.#@..
0

Output for the Sample Input

0
10
-1
3
2
1
6
4



Sample input:
3
...
.@.
...
3
.##
.#.
@##
3
##.
#..
@..
5
....@
##...
#....
...#.
##.##
5
#...#
...#.
#....
...##
..@..
5
#....
.....
.....
.....
..@..
5
#..#.
#.#.#
.#.#.
....#
.#@##
5
..##.
..#..
#....
#....
.#@..
0


Sample output:
0
10
-1
3
2
1
6
4

Submission status: Accepted

Solution code:
from collections import deque
import sys
readline = sys.stdin.readline
write = sys.stdout.write

dd0 = ((-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1))
DD = []
for k in range(6):
    ddk = []
    for y in range(k):
        for x in range(k):
            v = 0
            for dx, dy in dd0:
                nx = x + dx; ny = y + dy
                if not 0 <= nx < k or not 0 <= ny < k:
                    continue
                v |= 1 << (ny*k + nx)
            ddk.append(v)
    DD.append(ddk)
L = (1 << 16)
bc = [0]*L
for v in range(1, L):
    bc[v] = bc[v ^ (v & -v)] + 1

def solve():
    N = int(readline())
    if N == 0:
        return False
    dd = dd0
    dk = DD[N]
    state = 0
    for i in range(N):
        s = readline().strip()
        for j, c in enumerate(s):
            if c == '#':
                state |= 1 << (N*i + j)
            elif c == '@':
                sx = j; sy = i
    U = {(state, sx, sy): 0}
    que = deque([(state, sx, sy)])
    while que:
        state, x, y = key = que.popleft()
        d = U[key]
        if state == 0:
            write("%d\n" % d)
            break
        for dx, dy in dd:
            nx = x + dx; ny = y + dy
            if not 0 <= nx < N or not 0 <= ny < N:
                continue
            b = 1 << (ny*N + nx)
            if state & b:
                continue
            state ^= b
            n_state = 0
            for k in range(N*N):
                v = state & dk[k]
                if state & (1 << k):
                    if v and 2 <= bc[v // (v & -v)] <= 3:
                        n_state |= (1 << k)
                else:
                    if v and bc[v // (v & -v)] == 3:
                        n_state |= (1 << k)
            if n_state & b:
                n_state ^= b
            n_key = (n_state, nx, ny)
            if n_key not in U:
                U[n_key] = d+1
                que.append(n_key)
            state ^= b
    else:
        write("-1\n")
    return True
while solve():
    ...

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []
    oks = collections.defaultdict(set)

    def a2k(a, n):
        r = 0
        for i in range(n):
            for j in range(n):
                r *= 3
                r += a[i][j]
        return r

    def k2a(k, n):
        a = []
        for i in range(n):
            t = []
            for j in range(n):
                t.append(k%3)
                k //= 3
            a.append(t[::-1])
        return a

    def moves(a,n):
        si = sj = -1
        for i in range(n):
            for j in range(n):
                if a[i][j] == 2:
                    si = i
                    sj = j
                    break
            if si >= 0:
                break

        r = set()
        a[si][sj] = 0
        for i in range(max(0,si-1), min(n,si+2)):
            for j in range(max(0,sj-1), min(n,sj+2)):
                if a[i][j] != 0 or (si == i and sj == j):
                    continue
                a[i][j] = 2
                na = [[0]*n for _ in range(n)]
                zf = 1
                for k in range(n):
                    for l in range(n):
                        if a[k][l] == 2:
                            continue
                        c = 0
                        for m in range(max(0, k-1), min(n, k+2)):
                            for o in range(max(0, l-1), min(n, l+2)):
                                if m == k and o == l:
                                    continue
                                if a[m][o] > 0:
                                    c += 1
                        if (a[k][l] == 0 and c == 3) or (a[k][l] == 1 and 2 <= c <= 3):
                            na[k][l] = 1
                            zf = 0
                na[i][j] = 2
                if zf == 1:
                    return 'ok'
                r.add(a2k(na, n))
                a[i][j] = 0
        return r

    def f(n):
        sd = {}
        sd['.'] = 0
        sd['#'] = 1
        sd['@'] = 2
        a = [[sd[c] for c in S()] for _ in range(n)]
        zf = 1
        for i in range(n):
            for j in range(n):
                if a[i][j] == 1:
                    zf = 0
                    break
        if zf == 1:
            return 0
        r = inf
        d = collections.defaultdict(lambda: inf)
        k = a2k(a,n)
        q = set([k])
        d[k] = 0
        t = 0
        while q:
            t += 1
            nq = set()
            if q & oks[n]:
                return t
            for k in q:
                a = k2a(k,n)
                r = moves(a,n)
                if r == 'ok':
                    oks[n].add(k)
                    return t
                for nk in r:
                    if d[nk] > t:
                        d[nk] = t
                        nq.add(nk)
            q = nq
        return -1

    while 1:
        n = I()
        if n == 0:
            break
        rr.append(f(n))

    return '\n'.join(map(str, rr))


print(main())