2018-08-19 12:50

雑だけど解けたから転職するか〜。

require 'set'

MAP = <<-EOL
**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************
EOL

START = 'S'
GOAL  = 'G'
BLOCK = '*'
SPACE = ' '
ROUTE = '$'

data = MAP.split("\n").map { |line| line.chars }

start = nil
goal  = nil
edges = []

data.each_with_index do |line, y|
  line.each_with_index do |char, x|
    point = [x, y]
    case char
    when START
      start = point
      edges << point
    when GOAL
      goal = point
      edges << point
    when SPACE
      edges << point
    end
  end
end

paths = {}
edges.each do |edge|
  x, y = edge
  neighbors = [
    [x + 1, y],
    [x - 1, y],
    [x, y + 1],
    [x, y - 1]
  ].find_all { |e| edges.include?(e) }
  paths[edge] = neighbors
end

found = nil
history = Set.new
candidates = []

candidates << [start]

while !found
  new_candidates = []
  candidates.each do |route|
    edge = route.last
    if edge == goal
      found = route
      break
    end

    neighbors = paths[edge]
    neighbors.each do |e|
      next if history.include?(e)
      new_route = route + [e]
      new_candidates << new_route
    end

    history << edge
  end

  break if new_candidates.empty?
  candidates = new_candidates
end

if found
  found.each do |x, y|
    edge = data[y][x]
    data[y][x] = ROUTE if edge == SPACE
  end

  result = data.map { |line| line.join }.join("\n")
  puts result
else
  puts 'route not found.'
end