def calc_neighbours(node,path)
  length = Math.sqrt(path.length).to_i
  nbors = {}
  nbors[:right] = node+1 if node+1 >= 0 and (node+1)%length != 0 and path[node+1] != "W"
  nbors[:down] = node+length if node+length >= 0 and node+length < path.length and path[node+length] != "W"
  nbors[:up] = node-length if node-length >= 0 and path[node-length] != "W"
  nbors[:left] = node-1 if node-1 >= 0 and node%length != 0 and path[node-1] != "W"
  return nbors.values
end
 
def calc_path(path)
  path = path.split('')
  path.each_slice(Math.sqrt(path.length)) {|x| puts x.join(" ")}
  end_node = path.index("E")
  distance = Array(0..path.length).map! {|x| x = [0,(1/0.0)]}
  previous = Array(0..path.length)
  distance[0] = [0,0]
 
  while distance.min[0] != 1
    current = distance.index(distance.min)
    break if path[current] == "E"
    results = calc_neighbours(current,path)
    if distance[current][1] == (1/0.0)
      break
    end
    results.each do |x|
      if distance[current][1] + 1 < distance[x][1]
        distance[x][1] = distance[current][1] + 1
        previous[x] = current
      end
    end
    distance[current][0] = 1
  end
 
  if distance[end_node][1] != (1/0.0)
    puts "TRUE #{distance[end_node][1]}"
  else
    puts "FALSE"
  end
  stack = []
  while previous[current] != 0
    stack << previous[current]
    current = previous[current]
  end
  stack.each{|x| path[x] = "+"}
  path.each_slice(Math.sqrt(path.length)) {|x| puts x.join(" ")}
end
 
input = "8S...W....WW.W.W..W..W.W.......W.WWWWWWW.E...W...WW..WWW........."
calc_path(input[1..-1])

ZGVmIGNhbGNfbmVpZ2hib3Vycyhub2RlLHBhdGgpCiAgbGVuZ3RoID0gTWF0aC5zcXJ0KHBhdGgubGVuZ3RoKS50b19pCiAgbmJvcnMgPSB7fQogIG5ib3JzWzpyaWdodF0gPSBub2RlKzEgaWYgbm9kZSsxID49IDAgYW5kIChub2RlKzEpJWxlbmd0aCAhPSAwIGFuZCBwYXRoW25vZGUrMV0gIT0gIlciCiAgbmJvcnNbOmRvd25dID0gbm9kZStsZW5ndGggaWYgbm9kZStsZW5ndGggPj0gMCBhbmQgbm9kZStsZW5ndGggPCBwYXRoLmxlbmd0aCBhbmQgcGF0aFtub2RlK2xlbmd0aF0gIT0gIlciCiAgbmJvcnNbOnVwXSA9IG5vZGUtbGVuZ3RoIGlmIG5vZGUtbGVuZ3RoID49IDAgYW5kIHBhdGhbbm9kZS1sZW5ndGhdICE9ICJXIgogIG5ib3JzWzpsZWZ0XSA9IG5vZGUtMSBpZiBub2RlLTEgPj0gMCBhbmQgbm9kZSVsZW5ndGggIT0gMCBhbmQgcGF0aFtub2RlLTFdICE9ICJXIgogIHJldHVybiBuYm9ycy52YWx1ZXMKZW5kCiAKZGVmIGNhbGNfcGF0aChwYXRoKQogIHBhdGggPSBwYXRoLnNwbGl0KCcnKQogIHBhdGguZWFjaF9zbGljZShNYXRoLnNxcnQocGF0aC5sZW5ndGgpKSB7fHh8IHB1dHMgeC5qb2luKCIgIil9CiAgZW5kX25vZGUgPSBwYXRoLmluZGV4KCJFIikKICBkaXN0YW5jZSA9IEFycmF5KDAuLnBhdGgubGVuZ3RoKS5tYXAhIHt8eHwgeCA9IFswLCgxLzAuMCldfQogIHByZXZpb3VzID0gQXJyYXkoMC4ucGF0aC5sZW5ndGgpCiAgZGlzdGFuY2VbMF0gPSBbMCwwXQogCiAgd2hpbGUgZGlzdGFuY2UubWluWzBdICE9IDEKICAgIGN1cnJlbnQgPSBkaXN0YW5jZS5pbmRleChkaXN0YW5jZS5taW4pCiAgICBicmVhayBpZiBwYXRoW2N1cnJlbnRdID09ICJFIgogICAgcmVzdWx0cyA9IGNhbGNfbmVpZ2hib3VycyhjdXJyZW50LHBhdGgpCiAgICBpZiBkaXN0YW5jZVtjdXJyZW50XVsxXSA9PSAoMS8wLjApCiAgICAgIGJyZWFrCiAgICBlbmQKICAgIHJlc3VsdHMuZWFjaCBkbyB8eHwKICAgICAgaWYgZGlzdGFuY2VbY3VycmVudF1bMV0gKyAxIDwgZGlzdGFuY2VbeF1bMV0KICAgICAgICBkaXN0YW5jZVt4XVsxXSA9IGRpc3RhbmNlW2N1cnJlbnRdWzFdICsgMQogICAgICAgIHByZXZpb3VzW3hdID0gY3VycmVudAogICAgICBlbmQKICAgIGVuZAogICAgZGlzdGFuY2VbY3VycmVudF1bMF0gPSAxCiAgZW5kCiAKICBpZiBkaXN0YW5jZVtlbmRfbm9kZV1bMV0gIT0gKDEvMC4wKQogICAgcHV0cyAiVFJVRSAje2Rpc3RhbmNlW2VuZF9ub2RlXVsxXX0iCiAgZWxzZQogICAgcHV0cyAiRkFMU0UiCiAgZW5kCiAgc3RhY2sgPSBbXQogIHdoaWxlIHByZXZpb3VzW2N1cnJlbnRdICE9IDAKICAgIHN0YWNrIDw8IHByZXZpb3VzW2N1cnJlbnRdCiAgICBjdXJyZW50ID0gcHJldmlvdXNbY3VycmVudF0KICBlbmQKICBzdGFjay5lYWNoe3x4fCBwYXRoW3hdID0gIisifQogIHBhdGguZWFjaF9zbGljZShNYXRoLnNxcnQocGF0aC5sZW5ndGgpKSB7fHh8IHB1dHMgeC5qb2luKCIgIil9CmVuZAogCmlucHV0ID0gIjhTLi4uVy4uLi5XVy5XLlcuLlcuLlcuVy4uLi4uLi5XLldXV1dXV1cuRS4uLlcuLi5XVy4uV1dXLi4uLi4uLi4uIgpjYWxjX3BhdGgoaW5wdXRbMS4uLTFdKQ==