Got to get to the safe house and avoid the zombies.

zombie_wasteland.rb

class ZombieWasteland
  DEFAULT_WASTELAND = %q(@*^^^
                         zz*z.
                         **...
                         ^..*z
                         zz*zS)
  def initialize(wasteland=DEFAULT_WASTELAND)
    @wasteland = wasteland.gsub(' ', '')
  end

  def navigate
    # "Your brains have been eaten. You are now Undead."
    guess = Guess.new(@wasteland.gsub("@", '#'), 0)

    boards = accum(guess, [])
    min_score = boards.map { |b| b.score }.sort.first
    routes = boards.keep_if { |b| b.score == min_score }
    # routes.each { |r| puts r.wasteland }

    routes.last.wasteland
  end

  def accum(guess, result)
    if guess.completed
      # puts "Completed #{guess.score}"
      result << guess
      return result
    else
      guesses = guess.next_guesses
      guesses.each { |g| result + accum(g, result) }
      return result
    end
  end

end

class Guess
  attr_reader :score, :wasteland

  def initialize(wasteland, score, last_move = 0)
    @wasteland = wasteland
    @score = score
    @last_move = last_move
    @height = wasteland.lines.size
    @width = wasteland.lines[0].size
  end

  def completed
    ! @wasteland.include?("S")
  end

  def next_guesses
    valid_moves.map do |move|
      new_ws = @wasteland.clone
      new_ws[move] = '#'
      Guess.new(new_ws, @score + score_move(move), move)
    end
  end

  def valid_moves
    moves = [@last_move + 1, @last_move + @width, @last_move + @width + 1]
    if @last_move % @width != 0
      moves << @last_move + @width - 1
    end
    moves.keep_if { |m| is_valid?(m) }
  end

  def terrain(move)
    @wasteland[move]
  end

  def is_valid?(move)
    return false unless terrain(move)
    %q{. @ S * ^}.include?(terrain(move))
  end

  def score_move(move)
    terrain = terrain(move)
    return 1 if %q{. @ S}.include?(terrain)
    return 2 if '*' == terrain
    return 3 if '^' == terrain
    raise Exception.new("Unexpected move #{terrain}")
  end
end