# complete maze (mapped by hugging right wall without stopping at found)
maze = ''' ############### ### ########### ####### 
#...............#...#...........#.......#
#.#.###########.###.#.#.#########.#.#### 
#.#.....#...#.#.....#.#...........#.....#
 ######.#.#.#.#####.#.#################.#
#.......#.#...#.....#.#.....#.........#.#
#.#######.#####.#####.###.#.#.#######.#.#
#.#.....#.......#...#.#...#.#.....#.#.#.#
#.#.###.#########.#.#.#.###.#####.#.#.#.#
#...#.#.#...#.....#...#.#...#.....#...#.#
#.###.#.#.#.#.#########.#####.#####.###.#
#.....#...#.........#...#...#.....#.#...#
 ####.#### ########.#.###.#.#.###.#.###.#
#.........#.....#...#.#...#.#...#.#.#...#
#.#########.###.#.###.#.###.#####.#.#.#.#
#.#.......#.#.#.#.....#...#.......#...#.#
 ##.#####.#.#.#.#######.#.######## ####.#
#...#...#.#...#.......#.#.........#...#.#
#.#####.#.###.#######.#####.#####.#.###.#
#.#...#.#.....#.....#.#...#...#.#.#.....#
#.#.#.#.#######.###.#.#.#.###.#.#.###### 
#.#.#.....#.#...#.#.#.#.#.#.....#.#.....#
#.#.#####.#.#.###.#.###.#.#####.#.#.###.#
#.#.#.....#.......#.....#.....#.#...#...#
#.#.#.#################.#####.#.#####.#.#
#...#...#.............#.#.....#.#...#.#.#
 ### ##.#.#.#########.#.#.#######.#.#.#.#
#...#...#.#.#.....#.#...#...#.....#...#.#
#.###.#####.#.###.#.#######.###.#.#####.#
#...#.#.....#.#...#...#.....#...#.#...#.#
 ##.#.#.#####.#.#####.#.#####.#####.#.## 
#...#.#.#.....#.#.....#.....#.......#...#
#.###.#.#.#####.#.###.#####.#.#########.#
#...#...#.#.....#.#...#.....#.#...#.....#
 ##.#####.#####.#.#.###.#####.###.#.###.#
#...#.....#...#...#...#.#.........#.#...#
#.###.###.#.#.#### ##.#.#.#########.#.## 
#.....#.#.#.#.....#...#.#...#.....#.#.#.#
#.#####.#.#.#####.#####.#####.###.#.#.#.#
#.......#.......#.............#.....#...#
 ####### ####### ############# ##### ###'''

spaces = [[char == '.' for char in line] for line in maze.splitlines()]
# remaining = sum(sum(space) for space in spaces)
# use (y, x) as coordinates so that its easier to code
# source = (37, 7)
# 0 = north, 1 = east, 3 = south, 4 = west
# curr_pos = (37, 7)
# curr_dir = 3
# opp_of = [3, 4, 0, 1]

# def adj_spaces(curr_pos):
#   curr_y = curr_pos[0]
#   curr_x = curr_pos[1]
#   space = []
#   if spaces[curr_y - 1][curr_x]: # north
#     space.append()
#   space[1] = spaces[curr_y][curr_x + 1] # east
#   space[2] = spaces[curr_y + 1][curr_x] # south
#   space[3] = spaces[curr_y][curr_x - 1] # west
#   return space

max_step = 0
space_queue = [(37, 7, 0)] # contains triples (y, x, step)
# i = 0
while len(space_queue) > 0:
  print(space_queue)
  curr = space_queue.pop(0)
  curr_y = curr[0]
  curr_x = curr[1]
  curr_step = curr[2]
  spaces[curr_y][curr_x] = False
  if spaces[curr_y - 1][curr_x]: # north
    space_queue.append((curr_y - 1, curr_x, curr_step + 1))
  if spaces[curr_y][curr_x + 1]: # east
    space_queue.append((curr_y, curr_x + 1, curr_step + 1))
  if spaces[curr_y + 1][curr_x]: # south
    space_queue.append((curr_y + 1, curr_x, curr_step + 1))
  if spaces[curr_y][curr_x - 1]: # west
    space_queue.append((curr_y, curr_x - 1, curr_step + 1))
  if curr_step > max_step:
    max_step = curr_step

print(max_step)
# ans 344
cf5436710fddc9b5a334503d0fb7264e1977cfab
<mask token>

<mask token>
while len(space_queue) > 0:
    print(space_queue)
    curr = space_queue.pop(0)
    curr_y = curr[0]
    curr_x = curr[1]
    curr_step = curr[2]
    spaces[curr_y][curr_x] = False
    if spaces[curr_y - 1][curr_x]:
        space_queue.append((curr_y - 1, curr_x, curr_step + 1))
    if spaces[curr_y][curr_x + 1]:
        space_queue.append((curr_y, curr_x + 1, curr_step + 1))
    if spaces[curr_y + 1][curr_x]:
        space_queue.append((curr_y + 1, curr_x, curr_step + 1))
    if spaces[curr_y][curr_x - 1]:
        space_queue.append((curr_y, curr_x - 1, curr_step + 1))
    if curr_step > max_step:
        max_step = curr_step
print(max_step)

maze = """ ############### ### ########### ####### 
#...............#...#...........#.......#
#.#.###########.###.#.#.#########.#.#### 
#.#.....#...#.#.....#.#...........#.....#
 ######.#.#.#.#####.#.#################.#
#.......#.#...#.....#.#.....#.........#.#
#.#######.#####.#####.###.#.#.#######.#.#
#.#.....#.......#...#.#...#.#.....#.#.#.#
#.#.###.#########.#.#.#.###.#####.#.#.#.#
#...#.#.#...#.....#...#.#...#.....#...#.#
#.###.#.#.#.#.#########.#####.#####.###.#
#.....#...#.........#...#...#.....#.#...#
 ####.#### ########.#.###.#.#.###.#.###.#
#.........#.....#...#.#...#.#...#.#.#...#
#.#########.###.#.###.#.###.#####.#.#.#.#
#.#.......#.#.#.#.....#...#.......#...#.#
 ##.#####.#.#.#.#######.#.######## ####.#
#...#...#.#...#.......#.#.........#...#.#
#.#####.#.###.#######.#####.#####.#.###.#
#.#...#.#.....#.....#.#...#...#.#.#.....#
#.#.#.#.#######.###.#.#.#.###.#.#.###### 
#.#.#.....#.#...#.#.#.#.#.#.....#.#.....#
#.#.#####.#.#.###.#.###.#.#####.#.#.###.#
#.#.#.....#.......#.....#.....#.#...#...#
#.#.#.#################.#####.#.#####.#.#
#...#...#.............#.#.....#.#...#.#.#
 ### ##.#.#.#########.#.#.#######.#.#.#.#
#...#...#.#.#.....#.#...#...#.....#...#.#
#.###.#####.#.###.#.#######.###.#.#####.#
#...#.#.....#.#...#...#.....#...#.#...#.#
 ##.#.#.#####.#.#####.#.#####.#####.#.## 
#...#.#.#.....#.#.....#.....#.......#...#
#.###.#.#.#####.#.###.#####.#.#########.#
#...#...#.#.....#.#...#.....#.#...#.....#
 ##.#####.#####.#.#.###.#####.###.#.###.#
#...#.....#...#...#...#.#.........#.#...#
#.###.###.#.#.#### ##.#.#.#########.#.## 
#.....#.#.#.#.....#...#.#...#.....#.#.#.#
#.#####.#.#.#####.#####.#####.###.#.#.#.#
#.......#.......#.............#.....#...#
 ####### ####### ############# ##### ###"""
spaces = [[(char == '.') for char in line] for line in maze.splitlines()]
max_step = 0
space_queue = [(37, 7, 0)]
while len(space_queue) > 0:
    print(space_queue)
    curr = space_queue.pop(0)
    curr_y = curr[0]
    curr_x = curr[1]
    curr_step = curr[2]
    spaces[curr_y][curr_x] = False
    if spaces[curr_y - 1][curr_x]:
        space_queue.append((curr_y - 1, curr_x, curr_step + 1))
    if spaces[curr_y][curr_x + 1]:
        space_queue.append((curr_y, curr_x + 1, curr_step + 1))
    if spaces[curr_y + 1][curr_x]:
        space_queue.append((curr_y + 1, curr_x, curr_step + 1))
    if spaces[curr_y][curr_x - 1]:
        space_queue.append((curr_y, curr_x - 1, curr_step + 1))
    if curr_step > max_step:
        max_step = curr_step
print(max_step)

# complete maze (mapped by hugging right wall without stopping at found)
maze = ''' ############### ### ########### ####### 
#...............#...#...........#.......#
#.#.###########.###.#.#.#########.#.#### 
#.#.....#...#.#.....#.#...........#.....#
 ######.#.#.#.#####.#.#################.#
#.......#.#...#.....#.#.....#.........#.#
#.#######.#####.#####.###.#.#.#######.#.#
#.#.....#.......#...#.#...#.#.....#.#.#.#
#.#.###.#########.#.#.#.###.#####.#.#.#.#
#...#.#.#...#.....#...#.#...#.....#...#.#
#.###.#.#.#.#.#########.#####.#####.###.#
#.....#...#.........#...#...#.....#.#...#
 ####.#### ########.#.###.#.#.###.#.###.#
#.........#.....#...#.#...#.#...#.#.#...#
#.#########.###.#.###.#.###.#####.#.#.#.#
#.#.......#.#.#.#.....#...#.......#...#.#
 ##.#####.#.#.#.#######.#.######## ####.#
#...#...#.#...#.......#.#.........#...#.#
#.#####.#.###.#######.#####.#####.#.###.#
#.#...#.#.....#.....#.#...#...#.#.#.....#
#.#.#.#.#######.###.#.#.#.###.#.#.###### 
#.#.#.....#.#...#.#.#.#.#.#.....#.#.....#
#.#.#####.#.#.###.#.###.#.#####.#.#.###.#
#.#.#.....#.......#.....#.....#.#...#...#
#.#.#.#################.#####.#.#####.#.#
#...#...#.............#.#.....#.#...#.#.#
 ### ##.#.#.#########.#.#.#######.#.#.#.#
#...#...#.#.#.....#.#...#...#.....#...#.#
#.###.#####.#.###.#.#######.###.#.#####.#
#...#.#.....#.#...#...#.....#...#.#...#.#
 ##.#.#.#####.#.#####.#.#####.#####.#.## 
#...#.#.#.....#.#.....#.....#.......#...#
#.###.#.#.#####.#.###.#####.#.#########.#
#...#...#.#.....#.#...#.....#.#...#.....#
 ##.#####.#####.#.#.###.#####.###.#.###.#
#...#.....#...#...#...#.#.........#.#...#
#.###.###.#.#.#### ##.#.#.#########.#.## 
#.....#.#.#.#.....#...#.#...#.....#.#.#.#
#.#####.#.#.#####.#####.#####.###.#.#.#.#
#.......#.......#.............#.....#...#
 ####### ####### ############# ##### ###'''

spaces = [[char == '.' for char in line] for line in maze.splitlines()]
# remaining = sum(sum(space) for space in spaces)
# use (y, x) as coordinates so that its easier to code
# source = (37, 7)
# 0 = north, 1 = east, 3 = south, 4 = west
# curr_pos = (37, 7)
# curr_dir = 3
# opp_of = [3, 4, 0, 1]

# def adj_spaces(curr_pos):
#   curr_y = curr_pos[0]
#   curr_x = curr_pos[1]
#   space = []
#   if spaces[curr_y - 1][curr_x]: # north
#     space.append()
#   space[1] = spaces[curr_y][curr_x + 1] # east
#   space[2] = spaces[curr_y + 1][curr_x] # south
#   space[3] = spaces[curr_y][curr_x - 1] # west
#   return space

max_step = 0
space_queue = [(37, 7, 0)] # contains triples (y, x, step)
# i = 0
while len(space_queue) > 0:
  print(space_queue)
  curr = space_queue.pop(0)
  curr_y = curr[0]
  curr_x = curr[1]
  curr_step = curr[2]
  spaces[curr_y][curr_x] = False
  if spaces[curr_y - 1][curr_x]: # north
    space_queue.append((curr_y - 1, curr_x, curr_step + 1))
  if spaces[curr_y][curr_x + 1]: # east
    space_queue.append((curr_y, curr_x + 1, curr_step + 1))
  if spaces[curr_y + 1][curr_x]: # south
    space_queue.append((curr_y + 1, curr_x, curr_step + 1))
  if spaces[curr_y][curr_x - 1]: # west
    space_queue.append((curr_y, curr_x - 1, curr_step + 1))
  if curr_step > max_step:
    max_step = curr_step

print(max_step)
# ans 344