grid = [] w, h = 0, 0 def pprint(g): print "\n".join("".join(map(str, row)) for row in g) print def step(g, w, h): result = [[0] * (w - 1) for i in range(h - 1)] for y in range(h - 1): for x in range(w - 1): result[y][x] = int(g[y][x] + g[y + 1][x] + g[y][x + 1] + g[y + 1][x + 1] == 1) return result def bruteforce_answer(g): print "\n".join(map(str, g)) print answers = 0 w = len(g[0]) + 1 h = len(g) + 1 for i in xrange(2 ** (w * h)): temp = [[0] * w for n in range(h)] for y in range(h): for x in range(w): temp[y][x] = int(i & 1 << (x + w * y) > 0) if step(temp, w, h) == g: answers += 1 print "\n".join(map(str, temp)) print return answers def dfs_answer(g): global grid, w, h w = len(g[0]) h = len(g) if w < h: temp = [[0] * h for i in range(w)] for x in range(w): for y in range(h): temp[x][y] = g[y][x] w, h = h, w g = temp grid = g temp = [[0] * (w + 1) for i in range(h + 1)] firsthalf = [i[:] for i in temp] temp[0][0] = 1 return solve(firsthalf, 1) + solve(temp, 1) def goup(g, x, y): if y < 0: return g tot = g[y + 1][x - 1] + g[y][x - 1] + g[y + 1][x] possible = () if grid[y][x - 1]: if tot < 2: possible = (1 - tot,) else: return [] else: if tot < 2: possible = (tot,) else: possible = (0, 1) results = [] for p in possible: temp = [i[:] for i in g] temp[y][x] = p temp = goup(temp, x, y - 1) if temp: if type(temp[0][0]) is not list: temp = [temp] results += temp return results def goleft(g, x, y): if x < 0: return g[y] tot = g[y][x + 1] + g[y - 1][x + 1] + g[y - 1][x] possible = () if grid[y - 1][x]: if tot < 2: possible = (1 - tot,) else: return [] else: if tot < 2: possible = (tot,) else: possible = (0, 1) results = [] for p in possible: temp = [i[:] for i in g] temp[y][x] = p temp = goleft(temp, x - 1, y) if temp: if type(temp[0]) is not list: temp = [temp] results += temp return results def solve(g, n): if n > w: return 1 x = n y = min(n, h) prev = g[y - 1][x - 1] goal = grid[y - 1][x - 1] possible = [] if goal and prev: possible = [(0, 0, 0)] elif goal: possible = [(1, 0, 0), (0, 1, 0), (0, 0, 1)] elif prev: possible = [(1, 0, 0), (0, 1, 0), (0, 0, 1), (1, 1, 0), (0, 1, 1), (1, 0, 1), (1, 1, 1)] else: possible = [(0, 0, 0), (1, 1, 0), (0, 1, 1), (1, 0, 1), (1, 1, 1)] tot = 0 if n == 1: for p in possible: g[y][x] = p[0] g[y - 1][x] = p[1] g[y][x - 1] = p[2] tot += solve(g, n + 1) elif n != y: for p in possible: if g[y][x - 1] != p[2]: continue g[y][x] = p[0] g[y - 1][x] = p[1] g[y][x - 1] = p[2] for i in goup(g, x, y - 2): tot += solve(i, n + 1) else: for p in possible: g[y][x] = p[0] g[y - 1][x] = p[1] g[y][x - 1] = p[2] for i in goup(g, x, y - 2): for left in goleft(g, x - 2, y): i[y] = left tot += solve(i, n + 1) return tot olds2g = [ [ [[0, 0], [0, 0]], [[0, 0], [1, 1]], [[0, 1], [0, 1]], [[0, 1], [1, 0]], [[0, 1], [1, 1]], [[1, 0], [0, 1]], [[1, 0], [1, 0]], [[1, 0], [1, 1]], [[1, 1], [0, 0]], [[1, 1], [0, 1]], [[1, 1], [1, 0]], [[1, 1], [1, 1]], ], [[[0, 0], [0, 1]], [[0, 0], [1, 0]], [[0, 1], [0, 0]], [[1, 0], [0, 0]]], ] def old_hmerge(left, right): for l in left: for r in right: if l[0][1] == r[0][0]: l[1] += r[1] def old_vmerge(top, bottom): newt = [] for t in top: for b in bottom: if t[0][-1] == b[0][0] and t[1][-1] == b[1][0]: newt.append([i[:] for i in t]) newt[-1][0].append(b[0][1]) newt[-1][1].append(b[1][1]) return newt def old_answer(g): w = len(g[0]) h = len(g) possible = [[olds2g[g[y][x]][:] for y in range(h)] for x in range(w)] for x in range(w): for y in range(h): if x and g[y][x - 1]: del possible[x][y][8:] for x in range(w - 1, -1, -1): for y in range(1, h): possible[x][y] = old_vmerge(possible[x][y - 1], possible[x][y]) possible[x] = map(lambda n: [n, x == w - 1], possible[x][-1]) if x < w - 1: old_hmerge(possible[x], possible[x + 1]) possible[x] = filter(lambda x: x[1] > 0, possible[x]) return sum(i[1] for i in possible[0]) s2g = [ [ [0b00, 0b00], [0b01, 0b01], [0b01, 0b10], [0b10, 0b01], [0b10, 0b10], [0b00, 0b11], [0b01, 0b11], [0b10, 0b11], [0b11, 0b00], [0b11, 0b01], [0b11, 0b10], [0b11, 0b11], ], [[0b00, 0b01], [0b00, 0b10], [0b01, 0b00], [0b10, 0b00]], ] def hmerge(left, right): for l in left: for r in right: if l[0][1] == r[0][0]: l[1] += r[1] def vmerge(top, bottom): newt = [] for t in top: for b in bottom: if t[0] & 0x1 == (b[0] & 0x2) >> 1 and t[1] & 0x1 == (b[1] & 0x2) >> 1: newt.append(t[:]) newt[-1][0] = (newt[-1][0] << 1) | b[0] & 0x1 newt[-1][1] = (newt[-1][1] << 1) | b[1] & 0x1 return newt def answer(g): w = len(g[0]) h = len(g) possible = [[s2g[g[y][x]][: 8 if x and g[y][x - 1] else None] for y in range(h)] for x in range(w)] for x in range(w - 1): for y in range(h): if not g[y][x] and g[y][x + 1]: del possible[x][y][5:8] for x in range(w - 1, -1, -1): for y in range(1, h): possible[x][y] = vmerge(possible[x][y - 1], possible[x][y]) possible[x] = map(lambda n: [n, x == w - 1], possible[x][-1]) if x < w - 1: hmerge(possible[x], possible[x + 1]) # print len(possible[x]) possible[x] = filter(lambda x: x[1] > 0, possible[x]) # print '\t', len(possible[x]) return sum(i[1] for i in possible[0]) # from random import randint # # for x in range(test5size[0]): # for y in range(test5size[1]): # test5[y][x] = randint(0,1) # # test5[y][x] = (y * x) % 2 testcases = [ [[[1, 0], [0, 1]], 12], [[[1, 0, 1], [0, 1, 0], [1, 0, 1]], 4], [[[1, 0, 1, 0, 0, 1, 1, 1], [1, 0, 1, 0, 0, 0, 1, 0], [1, 1, 1, 0, 0, 0, 1, 0], [1, 0, 1, 0, 0, 0, 1, 0], [1, 0, 1, 0, 0, 1, 1, 1]], 254], [[[1, 1, 0, 1, 0, 1, 0, 1, 1, 0], [1, 1, 0, 0, 0, 0, 1, 1, 1, 0], [1, 1, 0, 0, 0, 0, 0, 0, 0, 1], [0, 1, 0, 0, 0, 0, 1, 1, 0, 0]], 11567], [[[0 for n in range(3)] for n in range(7)], 71482990], [ [ [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, 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, 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, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1], [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0], [0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0], [0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0], [1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1], ], 6363446530708320359469050394834135793398, ], [ [ [0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0], [0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0], [1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0], [1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0], [0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1], [1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0], [1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1], [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1], [1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1], ], 0, ], ] import time for case in enumerate(testcases): start = time.time() print "Case", case[0] print pprint(case[1][0]) print " Expected:", case[1][1] print "Calculated:", answer(case[1][0]) print "Time elapsed:", time.time() - start print "=" * 80