bfs

from collections import namedtuple, deque
Direction = namedtuple('Direction', 'dx, dy, letter')
FourDirections = [Direction(dx, dy, letter)
                  for dx, dy, letter in ((1, 0, 'S'), (-1, 0, 'N'), (0, 1, 'E'), (0, -1, 'W'))]
LetterToDirection = {d.letter: d for d in FourDirections}

def go(point, dir):
    return (point[0] + dir.dx, point[1] + dir.dy)

def at(lab, point):
    return lab[point[0]][point[1]]

ChainedCell = namedtuple('ChainedCell', 'cell, dir')
def unwind(came_from, last):
    path, cur = "", came_from.get(last)
    while cur:
        path = cur.dir.letter + path
        cur = came_from.get(cur.cell)
    print(path)
    return path

def find_way(maze, start, end):
    came_from = {start: False}
    next = deque([start])

    while len(next) > 0:
        cell = next.popleft()
        if cell == end:
            return True, unwind(came_from, cell)

        for dir in FourDirections:
            ncell = go(cell, dir)
            if at(maze, ncell) == '.' and came_from.get(ncell) is None:
                next.append(ncell)
                came_from[ncell] = ChainedCell(cell, dir)
    return False, None

if __name__ == '__main__':
    def waypts(start, way):
        r = set([start])
        cur = start
        for dsym in way:
            cur = go(cur, LetterToDirection[dsym])
            r.add(cur)
        return r

    maze = [
        "############",
        "#..........#",
        "###.####.###",
        "#..........#",
        "#.###.######",
        "#..#.......#",
        "##.######.##",
        "#.....#....#",
        "#####.#..#.#",
        "#.....######",
        "#.###......#",
        "############"]
    start, end = (1, 1), (10, 10)
    ok, way = find_way(maze, start, end)
    if ok:
        pts = waypts(start, way)
        print('\n'.join(''.join('w' if (y, x) in pts else c for x, c in enumerate(row)) for y, row in enumerate(maze)))
    else:
        print("Cannot find the way.")