# frozen_string_literal: true
 
class Maze
  NO_SOLUTION = 'No Solution'
 
  attr_accessor :field, :width, :height, :pos_x, :pos_y, :way, :step, :memo
 
  def self.solve(field)
    new(field).solve
  end
 
  def initialize(field)
    @field  = field.split($/).map { |e| e.split('') }
    @width  = @field.first.size
    @height = @field.size
    @pos_x, @pos_y = end_pos(?S)
    @step   = 0
    @memo   = {}
  end
 
  def end_pos(sym)
    @field.flatten.index(sym).divmod(@width).reverse
  end
 
  def movable
    [
      [@pos_x - 1, @pos_y, ?L],
      [@pos_x + 1, @pos_y, ?R],
      [@pos_x, @pos_y - 1, ?U],
      [@pos_x, @pos_y + 1, ?D]
    ].each_with_object([]) do |(x, y, way), ary|
      ary << way if (0...@width).include?(x) &&
                    (0...@height).include?(y) &&
                    @field[y][x] != ?# &&
                    @way != way
    end
  end
 
  def move(way)
    case way
    when ?L then @pos_x -= 1
    when ?R then @pos_x += 1
    when ?U then @pos_y -= 1
    when ?D then @pos_y += 1
    end
    @way = way
  end
 
  def set(x, y, step, way)
    @pos_x = x
    @pos_y = y
    @step = step
    @way = way
  end
 
  def solve
    ways = movable.each_with_object([]) do |way, ary|
      step = passed(way)
      ary << way unless step && @step >= step
    end
    return NO_SOLUTION if ways.empty?
    return @step + 1 if ways.any? { |way| symbol_in(way) == ?G }
    min = ways.map { |way| test_move(way) }.reject { |e| e == NO_SOLUTION }.min
    min ? min : NO_SOLUTION
  end
 
  def symbol_in(way)
    case way
    when ?L then @field[@pos_y][@pos_x - 1]
    when ?R then @field[@pos_y][@pos_x + 1]
    when ?U then @field[@pos_y - 1][@pos_x]
    when ?D then @field[@pos_y + 1][@pos_x]
    end
  end
 
  def test_move(test_way)
    pos_x, pos_y, step, way = @pos_x, @pos_y, @step, @way
    move(test_way)
    @memo[[@pos_x, @pos_y, test_way]] = @step += 1
    _step = solve
    set(pos_x, pos_y, step, way)
    _step
  end
 
  def passed(way)
    case way
    when ?L then @memo[[@pos_x - 1, @pos_y, way]]
    when ?R then @memo[[@pos_x + 1, @pos_y, way]]
    when ?U then @memo[[@pos_x, @pos_y - 1, way]]
    when ?D then @memo[[@pos_x, @pos_y + 1, way]]
    end
  end
 
end
 
 
[<<~EOT, <<~EOT, <<~EOT, <<~EOT].each { |s| puts "%s=> %s\n\n" %[s, Maze.solve(s)] }
  S....
  #....
  ..#..
  ....G
EOT
  S.....G
  .......
EOT
  S.#G
  ....
EOT
  S#G
EOT
 

IyBmcm96ZW5fc3RyaW5nX2xpdGVyYWw6IHRydWUKCmNsYXNzIE1hemUKICBOT19TT0xVVElPTiA9ICdObyBTb2x1dGlvbicKICAKICBhdHRyX2FjY2Vzc29yIDpmaWVsZCwgOndpZHRoLCA6aGVpZ2h0LCA6cG9zX3gsIDpwb3NfeSwgOndheSwgOnN0ZXAsIDptZW1vCiAgCiAgZGVmIHNlbGYuc29sdmUoZmllbGQpCiAgICBuZXcoZmllbGQpLnNvbHZlCiAgZW5kCiAgCiAgZGVmIGluaXRpYWxpemUoZmllbGQpCiAgICBAZmllbGQgID0gZmllbGQuc3BsaXQoJC8pLm1hcCB7IHxlfCBlLnNwbGl0KCcnKSB9CiAgICBAd2lkdGggID0gQGZpZWxkLmZpcnN0LnNpemUKICAgIEBoZWlnaHQgPSBAZmllbGQuc2l6ZQogICAgQHBvc194LCBAcG9zX3kgPSBlbmRfcG9zKD9TKQogICAgQHN0ZXAgICA9IDAKICAgIEBtZW1vICAgPSB7fQogIGVuZAogIAogIGRlZiBlbmRfcG9zKHN5bSkKICAgIEBmaWVsZC5mbGF0dGVuLmluZGV4KHN5bSkuZGl2bW9kKEB3aWR0aCkucmV2ZXJzZQogIGVuZAogIAogIGRlZiBtb3ZhYmxlCiAgICBbCiAgICAgIFtAcG9zX3ggLSAxLCBAcG9zX3ksID9MXSwKICAgICAgW0Bwb3NfeCArIDEsIEBwb3NfeSwgP1JdLAogICAgICBbQHBvc194LCBAcG9zX3kgLSAxLCA/VV0sCiAgICAgIFtAcG9zX3gsIEBwb3NfeSArIDEsID9EXQogICAgXS5lYWNoX3dpdGhfb2JqZWN0KFtdKSBkbyB8KHgsIHksIHdheSksIGFyeXwKICAgICAgYXJ5IDw8IHdheSBpZiAoMC4uLkB3aWR0aCkuaW5jbHVkZT8oeCkgJiYKICAgICAgICAgICAgICAgICAgICAoMC4uLkBoZWlnaHQpLmluY2x1ZGU/KHkpICYmCiAgICAgICAgICAgICAgICAgICAgQGZpZWxkW3ldW3hdICE9ID8jICYmCiAgICAgICAgICAgICAgICAgICAgQHdheSAhPSB3YXkKICAgIGVuZAogIGVuZAogIAogIGRlZiBtb3ZlKHdheSkKICAgIGNhc2Ugd2F5CiAgICB3aGVuID9MIHRoZW4gQHBvc194IC09IDEKICAgIHdoZW4gP1IgdGhlbiBAcG9zX3ggKz0gMQogICAgd2hlbiA/VSB0aGVuIEBwb3NfeSAtPSAxCiAgICB3aGVuID9EIHRoZW4gQHBvc195ICs9IDEKICAgIGVuZAogICAgQHdheSA9IHdheQogIGVuZAogIAogIGRlZiBzZXQoeCwgeSwgc3RlcCwgd2F5KQogICAgQHBvc194ID0geAogICAgQHBvc195ID0geQogICAgQHN0ZXAgPSBzdGVwCiAgICBAd2F5ID0gd2F5CiAgZW5kCiAgCiAgZGVmIHNvbHZlCiAgICB3YXlzID0gbW92YWJsZS5lYWNoX3dpdGhfb2JqZWN0KFtdKSBkbyB8d2F5LCBhcnl8CiAgICAgIHN0ZXAgPSBwYXNzZWQod2F5KQogICAgICBhcnkgPDwgd2F5IHVubGVzcyBzdGVwICYmIEBzdGVwID49IHN0ZXAKICAgIGVuZAogICAgcmV0dXJuIE5PX1NPTFVUSU9OIGlmIHdheXMuZW1wdHk/CiAgICByZXR1cm4gQHN0ZXAgKyAxIGlmIHdheXMuYW55PyB7IHx3YXl8IHN5bWJvbF9pbih3YXkpID09ID9HIH0KICAgIG1pbiA9IHdheXMubWFwIHsgfHdheXwgdGVzdF9tb3ZlKHdheSkgfS5yZWplY3QgeyB8ZXwgZSA9PSBOT19TT0xVVElPTiB9Lm1pbgogICAgbWluID8gbWluIDogTk9fU09MVVRJT04KICBlbmQKICAKICBkZWYgc3ltYm9sX2luKHdheSkKICAgIGNhc2Ugd2F5CiAgICB3aGVuID9MIHRoZW4gQGZpZWxkW0Bwb3NfeV1bQHBvc194IC0gMV0KICAgIHdoZW4gP1IgdGhlbiBAZmllbGRbQHBvc195XVtAcG9zX3ggKyAxXQogICAgd2hlbiA/VSB0aGVuIEBmaWVsZFtAcG9zX3kgLSAxXVtAcG9zX3hdCiAgICB3aGVuID9EIHRoZW4gQGZpZWxkW0Bwb3NfeSArIDFdW0Bwb3NfeF0KICAgIGVuZAogIGVuZAogIAogIGRlZiB0ZXN0X21vdmUodGVzdF93YXkpCiAgICBwb3NfeCwgcG9zX3ksIHN0ZXAsIHdheSA9IEBwb3NfeCwgQHBvc195LCBAc3RlcCwgQHdheQogICAgbW92ZSh0ZXN0X3dheSkKICAgIEBtZW1vW1tAcG9zX3gsIEBwb3NfeSwgdGVzdF93YXldXSA9IEBzdGVwICs9IDEKICAgIF9zdGVwID0gc29sdmUKICAgIHNldChwb3NfeCwgcG9zX3ksIHN0ZXAsIHdheSkKICAgIF9zdGVwCiAgZW5kCiAgCiAgZGVmIHBhc3NlZCh3YXkpCiAgICBjYXNlIHdheQogICAgd2hlbiA/TCB0aGVuIEBtZW1vW1tAcG9zX3ggLSAxLCBAcG9zX3ksIHdheV1dCiAgICB3aGVuID9SIHRoZW4gQG1lbW9bW0Bwb3NfeCArIDEsIEBwb3NfeSwgd2F5XV0KICAgIHdoZW4gP1UgdGhlbiBAbWVtb1tbQHBvc194LCBAcG9zX3kgLSAxLCB3YXldXQogICAgd2hlbiA/RCB0aGVuIEBtZW1vW1tAcG9zX3gsIEBwb3NfeSArIDEsIHdheV1dCiAgICBlbmQKICBlbmQKICAKZW5kCgoKWzw8fkVPVCwgPDx+RU9ULCA8PH5FT1QsIDw8fkVPVF0uZWFjaCB7IHxzfCBwdXRzICIlcz0+ICVzXG5cbiIgJVtzLCBNYXplLnNvbHZlKHMpXSB9CiAgUy4uLi4KICAjLi4uLgogIC4uIy4uCiAgLi4uLkcKRU9UCiAgUy4uLi4uRwogIC4uLi4uLi4KRU9UCiAgUy4jRwogIC4uLi4KRU9UCiAgUyNHCkVPVAo=