'''class LinkedStack:
    class _Node:
        __slots__ = '_element', '_next'
        def __init__(self , element ,next):
            self._element = element
            self._next = next
    def __init__(self):
        self._head = None
        self._size = 0
    def __len__(self):
        return self._size
    def is_empty(self):
        return self._size  == 0
    def push(self , e):
        self._head = self._Node(e, self._head)
        self._size  += 1
    def top(self):
        if self.is_empty ():
            raiseEmpty('Stack is  empty')
        return self._head._element
    def pop(self):
        if self.is_empty():
            raiseEmpty('Stack is  empty')
        answer = self._head._element
        self._head = self._head._next
        self._size  -= 1
        return answer

class LinkedQueue:
    class _Node:
        __slots__ = '_element', '_next'
        def __init__(self, element, next):
            self._element = elementself._next = next
    def __init__(self):
        self._head = None
        self._tail = None
        self._size = 0
    def __len__(self):
        return self._size
    def is_empty(self):
        return self._size  == 0
    def first(self):
        if self.is_empty ():
            raiseEmpty('Queue is  empty')
        return self._head._element
    def dequeue(self):
        if self.is_empty():
            raiseEmpty('Queue is  empty')
        answer = self._head._element
        self._head = self._head._next
        self._size  -= 1
        if self.is_empty ():
            self._tail = None
        return answer
    def enqueue(self , e):
        newest = self._Node(e, None)
        if self.is_empty ():
            self._head = newest
        else:
            self._tail._next = newest
        self._tail = newest
        self._size  += 1'''

import random
import sys

class Stack:
  def __init__(self):
    self._A = []
  def pop(self):
    self._A.pop()
  def push(self, obj):
    self._A.append(obj)
  def is_empty(self):
    return len(self._A) == 0

class Queue:
    def __init__(self):
        self._A = []
    def enqueue(self, obj):
        self._A.append(obj)
    def dequeue(self):
        self._A.pop(0)
    def is_empty(self):
        return len(self._A) == 0

class Maze:
  def __init__(self, size):
      self.maze_size = size
      self.goal_x = random.randint(0, self.maze_size + 1) #chooses random x coordinate within maze size for endpoint
      self.goal_y = random.randint(0, self.maze_size + 1) #chooses random y coordinate within maze size for endpoint

  def DrawMaze(self):
      visited = []
      x_s = stack()
      x_s.push(0)
      y_s = stack()
      y_s.push(0)
      while not x_s.is_empty() and y_s.is_empty():
        x_current = x_s.pop() #current x coordinate
        y_current = y_s.pop() #current y coordinate
        visited.append(x_current, y_current)
        temp = []  #will be list of unvisited coordinates surrounding (x_current, y_current)
        if (x_current + 1, y_current) not in visited:
          temp.append(x_current + 1, y_current)
        if (x_current - 1, y_current) not in visited:
          temp.append(x_current - 1, y_current)
        if (x_current, y_current + 1) not in visited:
          temp.append(x_current, y_current + 1)
        if (x_current, y_current - 1) not in visited:
          temp.append(x_current, y_current - 1)
        x_current, y_current = temp.pop(random.randint(0, len(temp) - 1))


  def TraverseMaze(self):
      visited = [] #visited coordinates
      x_q = Queue()
      x_q.enqueue(0)
      y_q = Queue()
      y_q.enqueue(0)
      while not x_q.is_empty() and y_q.is_empty():
        x_current = x_q.dequeue() #current x coordinate
        y_current = y_q.dequeue() #current y coordinate
        visited.append((x_current, y_current))
        if x_current == self.goal_x and y_current == self.goal_y: #if current coordinates is endpoint
          break
        if (x_current + 1, y_current) not in visited and :  #if reachable and unvisited, enqueue coordinates to right(coordinates east of current)
          x_q.enqueue(x_current + 1)
          y_q.enqueue(y_current)
        if (x_current, y_current + 1) not in visited and :  #if reachable and unvisited, enqueue coordinates below(coordinates south of current)
          x_q.enqueue(x_current)
          y_q.enqueue(y_current + 1)
        if (x_current - 1, y_current) not in visited and :  #if reachable and unvisited, enqueue coordinates to left(coordinates west of current)
          x_q.enqueue(x_current - 1)
          y_q.enqueue(y_current)
        if (x_current, y_current - 1) not in visited and :  #if reachable and unvisited, enqueue coordinates above(coordinates north of current)
          x_q.enqueue(x_current)
          y_q.enqueue(y_current - 1)

maze_size = int(input('please enter a maze size'))

#prints maze
'''def PrintMaze(maze):
    for row in range(maze_size):
        print(maze[row])
    print'''

'''#determines if coordinates are in bounds of maze
def InBounds(x,y):
    return (0 <= x < maze_size) and (0 <= y < maze_size)

def TraverseMaze(maze):          # traverse maze
    start = (0,0)
    s = Stack()
    s.push(start);               # push the start coordinates onto s
    while not s.is_empty():      #Loops until stack is empty
        (x, y) = s.pop()          # pop a coordinate off s into the tuple (x,y)
        if InBounds((x,y)):         # if (x,y) is on the maze then
            if maze[x][y] == 'G':    # if (x,y) is the goal then
                s.empty()             # empty the stack because we're done
            elif maze[x][y] == ' ':  # else if (x,y) is an undiscovered coordinate
                maze[x] = maze[x][:y] + 'D' + maze[x][y+1:]  # mark (x,y) discovered with 'D'
                PrintMaze(maze);      # print the maze to show progress so far
                s.push((x+1, y))      # push right neighbor onto stack s
                s.push((x-1, y))      # push left neighbor onto stack s
                s.push((x, y-1))      # push upper neighbor onto stack s
                s.push((x, y+1))      # push lower neighbor onto stack s'''