Problem:


Problem D: Weather Forecast

You are the God of Wind.

By moving a big cloud around, you can decide the weather: it invariably rains under the cloud,
and the sun shines everywhere else.

But you are a benign God: your goal is to give enough rain to every field in the countryside,
and sun to markets and festivals. Small humans, in their poor vocabulary, only describe this as
“weather forecast”.

You are in charge of a small country, called Paccimc. This country is constituted of 4 &times; 4 square
areas, denoted by their numbers.

Your cloud is of size 2 &times; 2, and may not cross the borders of the country.

You are given the schedule of markets and festivals in each area for a period of time.

On the first day of the period, it is raining in the central areas (6-7-10-11), independently of the
schedule.

On each of the following days, you may move your cloud by 1 or 2 squares in one of the four
cardinal directions (North, West, South, and East), or leave it in the same position. Diagonal
moves are not allowed. All moves occur at the beginning of the day.

You should not leave an area without rain for a full week (that is, you are allowed at most 6
consecutive days without rain). You don’t have to care about rain on days outside the period
you were given: i.e. you can assume it rains on the whole country the day before the period,
and the day after it finishes.

Input

The input is a sequence of data sets, followed by a terminating line containing only a zero.

A data set gives the number N of days (no more than 365) in the period on a single line, followed by N lines giving the schedule for markets and festivals. The i-th line gives the schedule for
the i-th day. It is composed of 16 numbers, either 0 or 1, 0 standing for a normal day, and 1 a
market or festival day. The numbers are separated by one or more spaces.

Output

The answer is a 0 or 1 on a single line for each data set, 1 if you can satisfy everybody, 0 if there
is no way to do it.

Sample Input

1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1
0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0
0

Output for the Sample Input

0
1
0
1



Sample input:
1
0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 1
0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 1
0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0
1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1
0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0
7
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0
0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0
0 1 0 0 0 0 0 1 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 1 0 0 0 0 1
0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0
15
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 1 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0
1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 1 0 1 0 1 0 0 0 0 0 0
0


Sample output:
0
1
0
1

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 = []
    mij = []
    for i in range(3):
        mi = []
        for j in range(3):
            mi.append([i*4+j,i*4+j+1,i*4+j+4,i*4+j+5])
        mij.append(mi)

    def f(n):
        a = [LI() for _ in range(n)]
        fs = set()
        def _f(i,j,d,d1,d4,d13,d16):
            if d >= n:
                return True
            key = (i,j,d,d1,d4,d13,d16)
            if key in fs:
                return False
            if i == 0:
                if j == 0:
                    d1 = d
                elif j == 2:
                    d4 = d
            elif i == 2:
                if j == 0:
                    d13 = d
                elif j == 2:
                    d16 = d
            for mm in mij[i][j]:
                if a[d][mm] > 0:
                    fs.add(key)
                    return False
            if d - min([d1,d4,d13,d16]) >= 7:
                fs.add(key)
                return False

            if _f(i,j,d+1,d1,d4,d13,d16):
                return True
            for ni in range(3):
                if i == ni:
                    continue
                if _f(ni,j,d+1,d1,d4,d13,d16):
                    return True
            for nj in range(3):
                if j == nj:
                    continue
                if _f(i,nj,d+1,d1,d4,d13,d16):
                    return True
            fs.add(key)
            return False

        if _f(1,1,0,-1,-1,-1,-1):
            return 1

        return 0

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

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


print(main())

Submission status: Accepted

Solution code:
from collections import deque
while True:
    n=int(input())
    if n==0:
        exit()
    data = []
    for i in range(n):
        tmp = list(map(int,input().split()))
        tmp = [tmp[:4],tmp[4:8],tmp[8:12],tmp[12:]]
        d = [ [0 for i in range(3)]for i in range(3)]
        for i in range(3):
            for j in range(3):
                for k in range(2):
                    for l in range(2):
                        d[i][j] += tmp[i+k][j+l]
        data.append(d)
    
    q = deque()
    memo = set()
    if data[0][1][1]:
        print(0)
        continue
    q.append((0,1,1,(0,0,0,0)))
    while len(q):
        z,y,x,h = q.popleft()
        if (y,x) == (0,0):
            h = (0,h[1]+1,h[2]+1,h[3]+1)
        elif (y,x) == (0,2):
            h = (h[0]+1,0,h[2]+1,h[3]+1)
        elif (y,x) == (2,0):
            h = (h[0]+1,h[1]+1,0,h[3]+1)
        elif (y,x) == (2,2):
            h = (h[0]+1,h[1]+1,h[2]+1,0)
        else:
            h = (h[0]+1,h[1]+1,h[2]+1,h[3]+1)
        if max(h)>6:
            continue
        if (z,y,x,h) in memo:
            continue
        memo.add((z,y,x,h))
        if z==n-1:
            print(1)
            break
        for i in range(3):
            if not data[z+1][i][x]:
                q.append((z+1,i,x,h))
            if not data[z+1][y][i]:
                q.append((z+1,y,i,h))
    else:
        print(0)