@memo = {}
def dfs(left,x=0,y=0)
    return 0 if (y < 0) || (y == 0 && x < 0) #
    pair = [x,y]
    return 0 if @memo[pair]              # 到達済みなら見ない
    return 1 if left == 1                # 最後のブロックを[x,y]に置いた
    @memo[pair] = true

    return dfs(left-1,x-1,y) + dfs(left-1,x,y-1) + dfs(left-1,x+1,y) + dfs(left-1,x,y+1)
end

p dfs(4)