#!/usr/bin/ruby
# Find path between upper left corner and lower right corner and mark
# them with '@'.

# Load input
maze = []
ARGF.each_line{|line| maze.push(line)}
height = maze.size
if height <= 0
   puts "Emtpy input"
   exit 1
end
if maze[0][0] != ' '
   puts "Upper left corner is not whitespace"
   exit 1
end
if maze[-1][-2] != ' '
   puts "Lower right corner is not whitespace"
   exit 1
end
width = maze[-1].size - 1

# Do a breadth-first expansion on all cells until we reach the goal.
visited = {}
visit_queue = [[0, 0, 0, 0]]
min_distance = (width * height) ** 2
point_closest_to_goal = [0, 0]
while visit_queue.size > 0
   py, px, y, x = visit_queue.shift
   if y < 0 || y >= height || x < 0 || maze[y][x] != ' '
      next
   end
   key = "#{y},#{x}"
   if visited[key]
      next
   end

   # Mark current cell as reachable, and store directions on how to get here
   visited[key] = [py, px]

   # Keep track of point that was closest to exit.  This is so that in
   # case if we generated an unsolvable maze, the solver will not get
   # stuck in an infinite loop.
   distance_to_exit = (height - 1 - y) ** 2 + (width - 1 - x) ** 2
   if min_distance > distance_to_exit
      min_distance = distance_to_exit
      point_closest_to_goal = [y, x]
      # Stop early when we have landed on exit
      if min_distance == 0
         break
      end
   end

   # Expand neighbors
   [[-1, 0], [1, 0], [0, -1], [0, 1]].each{|dy, dx|
      visit_queue.push([y, x, y + dy, x + dx])
   }
end

# Mark path from goal to start
y, x = point_closest_to_goal
begin
   maze[y][x] = '@'
   y, x = visited["#{y},#{x}"]
end until y == 0 && x == 0
maze[0][0] = '@'

maze.each{|line| puts line}