迷路

迷路

締め切りが 2018/01/27 10:00 AM なので，その 1 分後に投稿されるように予約



【概要】
右図のような迷路があります。
一歩で、上下左右に進めますが、太線は壁なので超えられません。
右図の a, b, c, d は、門を表しています。
門は開いているかもしれませんし、閉じているかもしれません。

開いている門・スタート地点・ゴール を指定します。
スタートからゴールに行くには最低何歩必要なのかを計算してください。
※入力で指定された門以外は、全て閉じているものとします

【入力】
入力は三文字で、
a8K
のようになっています。

開いている門・スタート・ゴール の3つが区切り文字なしで並んでいます。

【出力】
スタート地点からゴール地点まで何歩なのかを10進数で出力してください。
先ほどの入力の場合、a が通行可能であれば 8 から K まで 4歩で行けるので、
4
を出力すれば正解です。

【例】
入力
出力
状況
a8K
4

b9L
4

cAS
3

dR3
8


========================================

f = function(s) {
    d = matrix(
      c("6"," "," "," ", # 0 は 6 への径路
        "2"," "," "," ",
        "1","3","8"," ",
        "2","4"," "," ",
        "3","5","A"," ",
        "4"," "," "," ",
        "0","7"," "," ",
        "6","8","aD"," ",# gate 'a' 指定されたら小文字の a,b,c,d を取り径路候補に加える
        "2","7"," "," ",
        "A","F"," "," ",
        "4","9","G","dB",# gate 'd'
        "H","dA"," "," ",# gate'd'
        "D"," "," "," ",
        "C","J","a7"," ",# gate 'a'
        "K","bF"," "," ",# gate 'b'
        "9","bE"," "," ",# gate 'b'
        "A","cM"," "," ",# gate 'c'
        "B","N"," "," ",
        "J","O"," "," ",
        "D","I","K","P",
        "E","J","L"," ",
        "K"," "," "," ",
        "N","S","cG"," ",# gate 'c'
        "H","M","T"," ",
        "I","U"," "," ",
        "J"," "," "," ",
        "R","W"," "," ",
        "Q","S"," "," ",
        "M","R"," "," ",
        "N","Z"," "," ",
        "O","V"," "," ",
        "U","W"," "," ",
        "Q","V"," "," ",
        "Y"," "," "," ",
        "X","Z"," "," ",
        "T","Y"," "," "),36,byrow = TRUE)
    node = c(0:9, LETTERS)
    rownames(d) = node
    s = unlist(strsplit(s, ""))
    gate = s[1]
    d = sub(gate, "", d) # 指定されたゲートを開ける
    if (gate == "a") { # 指定以外のゲートは閉じるだけでなくパスから除く
      d = sub("[bcd][0-9A-Z]", " ", d)
    } else if (gate == "b") {
      d = sub("[acd][0-9A-Z]", " ", d)
    } else if (gate == "c") {
      d = sub("[abd][0-9A-Z]", " ", d)
    } else if (gate == "d") {
      d = sub("[abc][0-9A-Z]", " ", d)
    }
    start = c(s[2], " ", " ", " ")
    goal  = s[3]
    path = NULL

    push = function(x) { # パスのプッシュ
      rbind(x, path) ->> path
    }

    pop = function() { # パスのポップ
      if (is.null(path)) {
        push(start)
      }
      top = path[1,]
      path[-1,] ->> path
      return(top)
    }

    push(start)
    log = NULL
    repeat {
      x = pop()
      found = FALSE
      for (i in 1:4) {
        if (x[i] != " " && !x[i] %in% log) {
          log = c(x[i], log)
          found = TRUE
          break
        }
      }
      if (found) {
        if (x[i] == goal) {
          #cat("I got it!! ", rev(log), "\n")
          cat(length(log)-1)
          break
        }
        y = d[x[i],]
        x[i] = " "
        push(x)
        push(y)
      } else {
        log = log[-1]
      }
    }
}
#f(scan(file("stdin", "r"), what=""))

f("a8K") # 4
f("a8K") # 4
f("b9L") # 4
f("cAS") # 3
f("dR3") # 8
##
f("a5G") # 3
f("aBL") # 14
f("aAB") # 19
f("bP1") # 10
f("b5B") # 19
f("b7D") # 11
f("c1F") # 6
f("cXF") # 9
f("cFE") # 15
f("d0E") # 22
f("dC0") # 22
f("dMG") # 5