If you want a better explanation of bit masking, please ask and I'll write something together

If you want a better explanation of bit masking, please ask and I'll write something together.

EDIT: I threw together a working example, which uses bit masking and BFS (note that to change it to DFS you only have to edit current = self.paths.popleft() to current = self.paths.pop().

import collections
import string
import time

class MazeRunner:

    def __init__(self, file_path):
        self.maze = self.load_maze(file_path)
        self.Point = collections.namedtuple('Point', 'row col parent')
        self.paths = collections.deque()

    def load_maze(self, file_path):
        with open(file_path,'r') as f:
            maze = [list(line.rstrip()) for line in f.readlines()]
        maze_formatted = [["#_".find(l) for l in row] for row in maze]
        maze_formatted[-1] = [i*3 for i in maze_formatted[-1]]
        return maze_formatted

    def show_maze(self):
        for row in self.maze:
            s = ""
            for col in row:
                if str(col) in string.ascii_lowercase:
                    s += col
                else:
                    s += "# "[col&0b001]
            print(s)

    def neighbors(self, p):
        if p.row > 0 and self.maze[p.row-1][p.col] & 0b001:
            yield self.Point(p.row-1, p.col, p)
        if p.row < len(self.maze)-1 and self.maze[p.row+1][p.col] & 0b001:
            yield self.Point(p.row+1, p.col, p)
        if p.col > 0 and self.maze[p.row][p.col-1] & 0b001:
            yield self.Point(p.row, p.col-1, p)
        if p.col < len(self.maze[0])-1 and self.maze[p.row][p.col+1] & 0b001:
            yield self.Point(p.row, p.col+1, p)


    def solve(self):
        solution_found = False
        while self.paths:
            current = self.paths.popleft()
            if self.maze[current.row][current.col] & 0b010:
                solution_found = True
                print('Solution found!')
                break

            for point in self.neighbors(current):
                if not self.maze[point.row][point.col] & 0b100:
                    self.paths.append(point)
                    self.maze[point.row][point.col] |= 0b100;

        if not solution_found:
            return;

        final_path = []
        while current:
            final_path.append(current)
            current = current.parent

        final_path = final_path[::-1]
        for i, node in enumerate(final_path):
            self.maze[node.row][node.col] = string.ascii_lowercase[i%26]

    def find_path(self):
        start_col = self.maze[0].index(0b001)
        start_row = 0
        self.paths.append(self.Point(start_row, start_col, None))
        t0 = time.clock()
        self.solve()
        t1 = time.clock()
        print("Solution found in %.2fms" % ((t1-t0)*1000,))

def main():  

    path = "maze.txt"
    solver = MazeRunner(path)

    solver.find_path()
    solver.show_maze() 

if __name__ == "__main__":
    main()

This code always finds the (or rather one of) the shortest paths, and is about 5-10 times faster for some larger maze examples that I've tested it with.

Some initial impressions that I'd note if I was an interviewer:

1. if len(self.paths) < 1 is better written as if len(self.paths) == 0 or if not self.paths
2. In self.neighbors you perform a check to see if an adjacent node is outside the maze. Try moving this logic into self.adjacent
3. Instead of solving recursively, which will fail for mazes longer than 1000 steps, instead use a while self.paths or similar
4. If you want to improve speed slightly (at the cost of space), consider pre-allocating self.paths, by making it large and filled with None. Then you can have a pointer to the current index and manipulate in the same way. However this leads to its own issues
5. For further improvements, consider using BFS instead of your current DFS, and implementing a bidirectional search. This should in theory make the search up to twice as fast. However, there's nothing strictly wrong with what you have

Some initial impressions that I'd note if I was an interviewer:

1. if len(self.paths) < 1 is better written as if len(self.paths) == 0 or if not self.paths
2. In self.neighbors you perform a check to see if an adjacent node is outside the maze. Try moving this logic into self.adjacent
3. Instead of solving recursively, which will fail for mazes longer than 1000 steps, instead use a while self.paths or similar
4. If you want to improve speed slightly (at the cost of space), consider pre-allocating self.paths, by making it large and filled with None. Then you can have a pointer to the current index and manipulate in the same way. However this leads to its own issues
5. For further improvements, consider using BFS instead of your current DFS, and implementing a bidirectional search. This should in theory make the search up to twice as fast. However, there's nothing strictly wrong with what you have
6. Consider first parsing your maze and change it to an array of ints. You could use bit masking to store information about each flag. If you convert "#" => 0b0000, "_" => 0b0001, "-"/"+" => 0b0011, you can check if it is possible to access a neighbor by checking if self.maze[i][j] & 0b0001. You can check if you've reached your goal by doing if self.maze[i][j] & 0b0010. You can keep track of which nodes you've already visited and store that in the third bit with self.maze[i][j] |= 0b0100 and then check if you've visited a node using if self.maze[i][j] & 0b0100.

If you want a better explanation of bit masking, please ask and I'll write something together