=begin
Backtracking 을 이용하여 미로 탈출

=end

class Location
  attr_accessor :row, :col

end

class Maze
  attr_accessor :map_matrix, :height, :width

  attr_accessor :start

  WALL = '#'
  ROAD = ' '
  WALK = '+'
  START = 'S'
  GOAL = 'G'

  DIRECTION = [:NORTH, :WEST, :EAST, :SOUTH]

  def initialize()
    @map_matrix = []

  end

  def init_map(height, width)
    @height = height
    @width = width

    (0..@height).each do |i|
      @map_matrix[i] = []

      (0..@width).each { |j| @map_matrix[i][j] = ROAD }
    end
  end

  def print_maze
    puts "------------- Start Printing Maze ------------------"

    (0...@height).each do |i|
      (0...@width).each do |j|
        print @map_matrix[i][j]
      end

      puts
    end

    puts "------------- End of Printing Maze -----------------"
  end

  def Maze.init_example_maze()
=begin
* 예제 미로 모양
#G#######
#       #
### # ###
### #   #
#   ### #
# ###   #
# #S### #
# #     #
#########
=end

    maze = Maze.new
    maze.init_map(9, 9)

    maze.map_matrix[0] = [WALL, GOAL, WALL, WALL, WALL, WALL, WALL, WALL, WALL]
    maze.map_matrix[1] = [WALL, ROAD, ROAD, ROAD, ROAD, ROAD, ROAD, ROAD, WALL]
    maze.map_matrix[2] = [WALL, WALL, WALL, ROAD, WALL, ROAD, WALL, WALL, WALL]
    maze.map_matrix[3] = [WALL, WALL, WALL, ROAD, WALL, ROAD, ROAD, ROAD, WALL]
    maze.map_matrix[4] = [WALL, ROAD, ROAD, ROAD, WALL, WALL, WALL, ROAD, WALL]
    maze.map_matrix[5] = [WALL, ROAD, WALL, WALL, WALL, ROAD, ROAD, ROAD, WALL]
    maze.map_matrix[6] = [WALL, ROAD, WALL, START, WALL, WALL, WALL, ROAD, WALL]
    maze.map_matrix[7] = [WALL, ROAD, WALL, ROAD, ROAD, ROAD, ROAD, ROAD, WALL]
    maze.map_matrix[8] = [WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL, WALL]

    maze.start = Location.new
    maze.start.row = 6
    maze.start.col = 3

    maze
  end

  def Maze.load_maze(file_path)
    maze = Maze.new

    start_loc = Location.new

    maze_width = -1
    maze_height = 0

    File.open(file_path, "r") do |file|
      while line = file.gets

        line.chomp!

        line_len = line.length

        if -1 == maze_width
          maze_width = line_len
        else
          if line_len != maze_width
            puts "Maze data is not square!!!"
            return nil
          end
        end

        maze_height += 1
      end

      file.rewind

      maze.init_map(maze_height, maze_width)

      (0...maze_height).each do |i|
        line = file.gets

        line.chomp!

        line_arr = line.split(//)

        (0...maze_width).each do |j|
          maze.map_matrix[i][j] = line_arr[j]

          start_loc.row, start_loc.col = i, j if Maze::START == maze.map_matrix[i][j]
        end
      end

    end

    maze.start = start_loc
    maze
  end

end

class MazeExplorer
  
  def initialize(maze)
    @maze = maze
    
  end

  def solve_maze
    if move(@maze.start)
      @maze.map_matrix[@maze.start.row][@maze.start.col] = Maze::START
      @maze.print_maze
    else
      puts("No Way to Exit!!")
    end

  end

  def move(curr)
    return nil if !check_valid(curr)

    return true if Maze::GOAL == @maze.map_matrix[curr.row][curr.col]

    @maze.map_matrix[curr.row][curr.col] = Maze::WALK

    Maze::DIRECTION.each do |dir|
      new_loc = Location.new

      new_loc.row, new_loc.col = curr.row, curr.col

      case dir
      when :NORTH
        new_loc.row = curr.row - 1
      when :WEST
        new_loc.col = curr.col - 1
      when :EAST
        new_loc.col = curr.col + 1
      when :SOUTH
        new_loc.row = curr.row + 1
      end

      return true if move(new_loc)
    end

    # move to new Direction : ALL nil // do backtracking
    @maze.map_matrix[curr.row][curr.col] = Maze::ROAD

    return nil
  end

  def check_valid(curr)
    return nil if curr.row < 0 || curr.row >= @maze.height
    
    return nil if curr.col < 0 || curr.col >= @maze.width

    if Maze::WALL == @maze.map_matrix[curr.row][curr.col] ||
        Maze::WALK == @maze.map_matrix[curr.row][curr.col]
        return nil
    end

    return true
  end

end

maze = Maze.init_example_maze
#maze = Maze.load_maze("MazeSample.dat")

person = MazeExplorer.new(maze)
person.solve_maze

------------- Start Printing Maze ------------------
#G#######
#+++++  #
### #+###
### #+++#
#   ###+#
# ###  +#
# #S###+#
# #+++++#
#########
------------- End of Printing Maze -----------------