目標を達成する手順は何通り？
締め切りが 2017/06/20 10:00 AM なので，その 1 分後に投稿されるように予約
設問
こども向けのプログラミング教育が話題です。
ソースコードを書くというよりは、論理的な思考を養うことが求められ、小学校低学年のこどもにもイメージしやすい例が使われています。
例えば、横に m マス、縦に n マスの格子状のマスを左上から右下に移動するための手順を考える、という例があります。
使用可能な操作は「前に進む」「左を向く」「右を向く」の3つです。
このマスの外側には移動できず、最短の経路である必要はありません。
なお、右下のマスに着くとその時点で終了とします。
（つまり、右下のマスでは「左を向く」「右を向く」の操作はできません。）
m = 3, n = 2で、右向きに開始するとき、以下の4回の操作で左図のように移動できます。
1. 前に進む
2. 前に進む
3. 右を向く
4. 前に進む
では、左上から右下に5回の操作で移動させるにはどうすればよいでしょうか？
例えば、左上の位置で最初の向きを下向きの状態にしておけば、以下の5回の操作で右図のように移動できます。
1. 左を向く
2. 前に進む
3. 前に進む
4. 右を向く
5. 前に進む
標準入力から m、n、操作する回数がスペース区切りで与えられます。
このときの操作方法が何通りあるかを求め、標準出力に出力してください。
例えば、 m = 3, n = 2のとき、5回の操作で移動する方法は上記の右図の他に4通りあり、合計5通りですので、以下のように出力します。
なお、入力として用いられる値は、出力が32bit整数の範囲内となるものとします。
【入出力サンプル】
標準入力
3 2 5
標準出力
5
===============================================
時間制限をクリアできない
tricombinations = function (p) {
retval = matrix(" ", nrow = 3^p, ncol = p)
for (n in 1:p) {
retval[, n] = rep(c(rep("R", (3^p/3^n)), rep("L", (3^p/3^n)), rep("F", (3^p/3^n))),
length = 3^p)
}
retval
}
g = function(m, n, step, a, e, dx, dy) {
p = m*n
r = apply(e, 1, function(s) {
x = y = 2
for (i in seq_len(step)) {
dxy = dx*2+dy
if (s[i] == "R") { # 右旋回
if (dxy == 2) { # dx = 1, dy = 0
dx = 0
dy = 1
} else if (dxy == -2) { # dx = -1, dy = 0
dx = 0
dy = -1
} else if (dxy == 1) { # dx = 0, dy = 1
dx = -1
dy = 0
} else { # dx = 0, dy = -1
dx = 1
dy = 0
}
} else if (s[i] == "L") { # 左旋回
if (dxy == 2) { # dx = 1, dy = 0
dx = 0
dy = -1
} else if (dxy == -2) { # dx = -1, dy = 0
dx = 0
dy = 1
} else if (dxy == 1) { # dx = 0, dy = 1
dx = 1
dy = 0
} else { # dx = 0, dy = -1
dx = -1
dy = 0
}
} else { # if (s[i] == "F") 前進
x = x+dx
y = y+dy
}
if (a[x, y] == 0) { # はみ出した
return(0)
} else if (a[x, y] == 2) { # 出口
return(i)
}
}
return(0) # 途中
})
return(sum(r == step))
}
f = function(m, n, step) {
a = matrix(0, n+2, m+2)
a[1:n+1, 1:m+1] = 1
a[n+1, m+1] = 2
e = tricombinations(step)
count = g(m, n, step, a, e, 1, 0) # dxy = 2*dx+dy = 2
count = count + g(m, n, step, a, e, -1, 0) # dxy = -2
count = count + g(m, n, step, a, e, 0, 1) # dxy = 1
count = count + g(m, n, step, a, e, 0, -1) # dxy = -1
cat(count)
}
f(3, 2, 5) # 5
f(6, 6, 12) # 12
f(8,3, 20)
f(80,80,162)
f(77,13,96) #
