ヘックス上の最長狭義単調増加列

ヘックス上の最長狭義単調増加列
締切が 2016/12/29 10:00 AM なので，その 1 分後に投稿されるように予約

【概要】
1辺4マスの六角形状のマス目があり、各マスにはa〜zの文字が入っています。
a〜zの文字は、1〜26 の数を表しています。
適当なマス目から隣のマスへ隣のマスへとたどり、どんどん増えていく数列（狭義単調増加列）を作ることを考えます。

入力で与えられる配置の場合に作ることができる狭義単調増加列の中で、もっとも要素数が多いものの要素数を計算するプログラムを書いてください。

【入出力】

入力は
javc/fhqvv/nerncj/actuybv/unrutf/sxgff/xjdi
こんな感じで標準入力から来ます。

マス目の東西の一列が、北から順にスラッシュ(/)区切りで並んでいます。

出力は、最長の狭義単調増加列の要素数を、10進数で。
先程の例だと左図のように，緑色の線が最長となる場合の例になりますので、
10
を出力すると正解です。

　　

【例】
入力                        出力     状況
javc/fhqvv/nerncj/actuybv/unrutf/sxgff/xjdi    10     左図
kmyv/fuhxe/hhnnvr/dygmgwo/jbwkfu/zqthb/jxbl     9     右図

【補足】
    不正な入力に対処する必要はありません。
    長さ1でも狭義単調増加列になります。考えられる最小値は 1 になります。
    a, d, f, x のように、ちゃんと毎回増えること。a, n, n, x のようなものは NG。

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

# ヘックスの番号
#        1   2   3   4
#      5   6   7   8   9
#   10  11  12  13  14  15
# 16  17  18  19  20  21  22
#   23  24  25  26  27  28
#     29  30  31  32  33
#       34  35  36  37

# r[[i]] は，i 番目のヘックスに隣接するヘックスの番号のリスト
r = vector("list", 37)
r[[1]] = c(2, 5, 6)
r[[2]] = c(1, 3, 6, 7)
r[[3]] = c(2, 4, 7, 8)
r[[4]] = c(3, 8, 9)
r[[5]] = c(1, 6, 10, 11)
r[[6]] = c(1, 2, 5, 7, 11, 12)
r[[7]] = c(2, 3, 6, 8, 12, 13)
r[[8]] = c(3, 4, 7, 9, 13, 14)
r[[9]] = c(4, 8, 14, 15)
r[[10]] = c(5, 11, 16, 17)
r[[11]] = c(5, 6, 10, 12, 17, 18)
r[[12]] = c(6, 7, 11, 13, 18, 19)
r[[13]] = c(7, 8, 12, 14, 19, 20)
r[[14]] = c(8, 9, 13, 15, 20, 21)
r[[15]] = c(9, 14, 21, 22)
r[[16]] = c(10, 17, 23)
r[[17]] = c(10, 11, 16, 18, 23, 24)
r[[18]] = c(11, 12, 17, 19, 24, 25)
r[[19]] = c(12, 13, 18, 20, 25, 26)
r[[20]] = c(13, 14, 19, 21, 26, 27)
r[[21]] = c(14, 15, 20, 22, 27, 28)
r[[22]] = c(15, 21, 28)
r[[23]] = c(16, 17, 24, 29)
r[[24]] = c(17, 18, 23, 25, 29, 30)
r[[25]] = c(18, 19, 24, 26, 30, 31)
r[[26]] = c(19, 20, 25, 27, 31, 32)
r[[27]] = c(20, 21, 26, 28, 32, 33)
r[[28]] = c(21, 22, 27, 33)
r[[29]] = c(23, 24, 30, 34)
r[[30]] = c(24, 25, 29, 31, 34, 35)
r[[31]] = c(25, 26, 30, 32, 35, 36)
r[[32]] = c(26, 27, 31, 33, 36, 37)
r[[33]] = c(27, 28, 32, 37)
r[[34]] = c(29, 30, 35)
r[[35]] = c(30, 31, 34, 36)
r[[36]] = c(31, 32, 35, 37)
r[[37]] = c(32, 33, 36)

search = function(x, start) {
    # アルファベット列 x で，start 番目のヘックスからの径路を探索
    path = vector("list", 37) # 次のヘックス番号の候補リスト
    PATH = integer(37) # それまでにたどってきたヘックスの番号リスト
    i = 1
    path[[i]] = start
    mx = 0 # 最長径路
    repeat {
        if (length(path[[i]]) == 0) { # このノードから次のヘックス探索は終了
            i = i - 1 # 一つ前のリストに戻って繰り返し
            if (i == 0) { # 全部探索したら終わり
                break
            }
        }
        PATH[i] = start = path[[i]][1] # リストの先頭を start にして
        path[[i]] = path[[i]][-1] # 先頭を取り除く（処理済みにする）
        nxt = r[[start]] # 隣接するヘックス番号ベクトル
        nxt = nxt[x[start] < x[nxt]] # そのうちで，より大きなアルファベットのもの
        valid = setdiff(nxt, PATH) # さらに，既に通ってきたヘックス番号ではないもの
        if (length(valid) > 0) { # 次のヘックスに移動できる（径路がある）
            i = i + 1
            path[[i]] = valid # 径路の候補をリストアップ
            if (i  > mx) { # 最長経路の更新
                PATH0 = c(PATH[1:(i-1)], valid[1]) # 径路のヘックス番号ベクトル
                mx = i # 径路の長さ
            }
        }
    }
    PATH0 # 最長経路のヘックス番号ベクトル
}

f = function(s) {
    x = unlist(strsplit(gsub("/", "", s), ""))
    mx = 1 # デフォルトの最短経路は長さ 1
    for (start in seq_along(r)) { # すべてのヘックスをチェック
        # 周りのどのヘックスよりも小さいアルファベットなら本当のスタート候補
        if (all(x[start] < x[r[[start]]])) { # 周りのどのヘックスよりも小さいアルファベット
            path = search(x, start) # start から始まる径路を捜す（径路のヘックス番号ベクトルを返す）
            if (length(path) > mx) {
                mx = length(path) # 最長経路の更新
                path.max = path # 実際の径路のヘックス番号の更新
            }
        }
    }
#    cat(path.max)
    cat(mx)
}

f("javc/fhqvv/nerncj/actuybv/unrutf/sxgff/xjdi") # 10
f("kmyv/fuhxe/hhnnvr/dygmgwo/jbwkfu/zqthb/jxbl") # 9
f("ukps/kjcrl/ymfsqq/kbzfidr/dktjby/submc/ktps") # 8
f("zxgm/jzcwp/yacivm/ibckuek/bgoznq/svqfp/gfwn") # 7
f("pfqr/qvplf/kkrxqk/tbvravh/hurwxp/vnvwv/xjzt") # 6
f("onjw/cmtxj/jntmsv/ffttgre/sxsveu/deuey/qygd") # 5
f("neoo/boifu/dpgzxz/jhlqwwi/oijunp/fseev/tpwj") # 11
f("abcd/rstue/qpqrvf/povwswg/onutxh/nmzyi/mlkj") # 26
f("dddd/dcccd/dcbbcd/dcbabcd/dcbbcd/dcccd/dddd") # 4
f("gggg/ffffg/eeeefg/ddddefg/cccdef/bbcde/abcd") # 7
f("kjih/xyzag/wvutbf/jklmsce/ihgnrd/bcfoq/adep") # 26
f("dddd/ddddd/ccccdd/cccccdd/bbbccd/bbbcc/abbc") # 2
f("mmmm/mmmmm/mmmmmm/mmmmmmm/mmmmmm/mmmmm/mmmm") # 1
f("yxwv/zkjiu/slcbht/rmdagst/qnefru/popqv/zyxw") # 26