ascii maze

gistfile1.txt

'''
### ASCII Maze Master

Write a program that will find a path through a simple maze. A simple maze in this context is a maze where all of the walls are connected to each other. Take this example maze segment.

```
# # ### #
# #
# ### B #
#   # B #
# B # B #
# B   B #
# BBBBB #
#       #
#########
```

See how the wall drawn with Bs isn't connected to any other walls? That's called a floating wall. A simple maze contains no floating walls - ie. there are no loops in the maze.

#### Formal Inputs and Outputs

##### Input Description

You will be given two numbers X and Y. After that you will be given a textual ASCII grid, X wide and Y tall, of walls # and spaces. In the maze there will be exactly one letter S and exactly one letter E. There will be no spaces leading to the outside of the maze - ie. it will be fully walled in.

##### Output Description

You must print out the maze. Within the maze there should be a path drawn with `.` leading from the letter S to the letter E. Try to minimise the length of the path if possible - don't just fill all of the spaces with `.`!
Sample Inputs & Output

##### Sample Input

15x15
```
###############
#S        #   #
### ### ### # #
#   #   #   # #
# ##### ##### #
#     #   #   #
# ### # ### ###
# #   # #   # #
# # ### # ### #
# # # # # #   #
### # # # # # #
#   #   # # # #
# ####### # # #
#           #E#
###############
```

Sample Output

```
###############
#S..      #   #
###.### ### # #
#...#   #   # #
#.##### ##### #
#.....#   #   #
# ###.# ### ###
# #...# #   # #
# #.### # ### #
# #.# # # #...#
###.# # # #.#.#
#...#   # #.#.#
#.####### #.#.#
#...........#E#
###############
```
'''

maze = '''
#########################################
#   #       #     #           #         #
# # # ### # # ### # ####### ### ####### #
# #S#   # #   #   # #     #           # #
# ##### # ######### # # ############# # #
# #     # #         # #       #   #   # #
# # ##### # ######### ##### # # # # ### #
# #     #   #     #     #   # # # # # # #
# ##### ######### # ##### ### # # # # # #
#   #           #   #     #   # # #   # #
# ### ######### # ### ##### ### # ##### #
#   #   #     # # #   #       # #       #
# # ### # ### # ### ### ####### ####### #
# #     # #   #     #   # #     #     # #
# ####### # ########### # # ##### # ### #
#     # # #   #       #   # #   # #     #
##### # ##### # ##### ### # ### # #######
#   # #     # #   #   #   # #   #     # #
# ### ### ### ### # ### ### # ####### # #
#   #     #   #   # #   #   # #     #   #
### ##### # ### ### ### # ### # ### ### #
#       # #   # # #   # # #   # # #     #
# ####### ### # # ### ### # ### # #######
#       #   #   #   # #   #     #       #
# ##### ### ##### # # # ##### ### ### ###
#   # # #   #     # # #     # #     #   #
### # # # ### # ##### # ### # # ####### #
# #   #   #   # #     #   # # # #     # #
# ### ##### ### # ##### ### # # # ### # #
#   #       #   # # #   #   # # #   #   #
# # ######### ### # # ### ### # ### #####
# #     #   # # # #   #   # # #   #     #
# ##### # # # # # ### # ### # ######### #
# #   # # # # # #   # #   #             #
# # # # # # # # ### ### # ############# #
# # #     # # #   #   # #       #       #
# ######### # # # ### ### ##### # #######
#     #     # # #   #   # #     # #     #
# ### ####### ### # ### ### ##### # ### #
#   #             #   #     #       #E  #
#########################################
'''

def find_char(matrix, char):
    
    for i, row in enumerate(matrix):
        for j, ch in enumerate(row):
            if ch == char:
                return [i,j]
            

def search(matrix, i, j):
    
    queue = []
    
    queue.append([(i,j)])
    
    visited = set()
    
    visited.add((i,j))
    
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    
    while len(queue):
        path = queue.pop(0)

        current_point = path[-1]

        sx, sy = current_point
        
        for dx, dy in directions:
            x, y = sx + dy, sy + dx
            current_path = path.copy()
            
            if matrix[x][y] == "#":
                continue
            
            if (x,y) not in visited:
                visited.add((x,y))
                
                current_path.append((x,y))
                queue.append(current_path)
                
            if matrix[x][y] == "E":
                return current_path
        
            
def paint(matrix, path):
    
    for point in path:
        x, y = point
        matrix[x][y] = "."


def solve_maze(maze, x, y):
    
    matrix = []
    
    rows = maze.strip().split('\n')
    
    for row in rows:
        l = []
        for c in row:
            l.append(c)
        matrix.append(l)
    
    
    a = find_char(matrix, "S")
    i, j = a[0], a[1]
    
    path = search(matrix, i, j)
    paint(matrix, path)
    
    return matrix
    




m = solve_maze(maze, 15, 15)

print('\n'.join([''.join(line) for line in m]))


'''
def parse_maze():


def find_char():


def find_solution():
  # find start
  # initiate queue (list of paths)
  # initiate visited (set of all points traveled)
  # from starting find all possible path
  # add all possible points as new path to queue
  

'''