import copy
from random import randint

WALL = 0
EMPTY = 1
PATH = 2
DEAD = 3


class CS235Maze(object):
    def __init__(self, data):
        self._data = data
        self._size = len(data)

    def _solve(self, x, y, z, path):
        if x < 0 or y < 0 or z < 0 or \
                x >= self._size or y >= self._size or z >= self._size:
            return False
        elif self._data[x][y][z] != EMPTY:
            return False
        elif x == self._size - 1 and y == self._size - 1 \
                and z == self._size - 1:
            self._data[x][y][z] = PATH
            path.append((x, y, z))
            return True
        else:
            self._data[x][y][z] = PATH
            if self._solve(x - 1, y, z, path) or \
                    self._solve(x + 1, y, z, path) or \
                    self._solve(x, y - 1, z, path) or \
                    self._solve(x, y + 1, z, path) or \
                    self._solve(x, y, z - 1, path) or \
                    self._solve(x, y, z + 1, path):
                path.append((x, y, z))
                return True
            else:
                self._data[x][y][z] = DEAD
                return False

    def solve(self):
        path = []
        success = self._solve(0, 0, 0, path)
        path.reverse()
        return success, path

    def __str__(self):
        r = derp_transpose(self._data, self._size)
        rs = ''
        for i in xrange(self._size):
            for j in xrange(self._size):
                for k in xrange(self._size):
                    rs += '{} '.format(r[i][j][k])
                rs += '\n'
            rs += '\n'
        return rs


def make_maze(size=8):
    r = []
    for i in xrange(size):
        r.append([])
        for j in xrange(size):
            r[i].append([randint(0, 1) for k in xrange(size)])
    r[0][0][0] = 1
    r[size - 1][size - 1][size - 1] = 1
    return CS235Maze(r)


def parse_maze(maze):
    maze = maze.replace('\r', '')
    soilded = [[[int(i) for i in j.split()]
                for j in k.split('\n')]
               for k in maze.split('\n\n') if k]
    cleaned = derp_transpose(soilded, size=len(soilded))
    return CS235Maze(cleaned)


def derp_transpose(s, size=8):
    r = copy.deepcopy(s)
    for i in xrange(size):
        for j in xrange(size):
            for k in xrange(size):
                r[i][j][k] = s[k][j][i]
    return r