DouKaku?

(defun count-paths (width height &rest edges-na)
  (let ((table (make-array (list height width) :initial-element 0)))
    (dotimes (h height)
      (dotimes (w width)
        (if (or (zerop w) (zerop h))
            (setf (aref table h w) 1)
          (progn
            (unless (find (list (1- w) h w h) edges-na :test #'equal)
              (incf (aref table h w) (aref table h (1- w))))
            (unless (find (list w (1- h) w h) edges-na :test #'equal)
              (incf (aref table h w) (aref table (1- h) w)))))))
    ;; (print table)
    (aref table (1- height) (1- width))
    ))

;; test
(count-paths 4 5)
(count-paths 4 5 '(1 1 1 2) '(2 2 3 2) '(1 3 2 3))

using System;

class Program
{
    static void Main()
    {
        Console.WriteLine(Route1(3, 4));
        Console.WriteLine(Route2(3, 4));
    }

    static int Route1(int x, int y)
    {
        //スタート地点
        if (x == 0 && y == 0)
        {
            return 1;
        }
        //左からのルートと上からのルートの合計
        return (x > 0 ? Route1(x - 1, y) : 0) + (y > 0 ? Route1(x, y - 1) : 0);
    }

    static int Route2(int x, int y)
    {
        if (x == 0 && y == 0)
        {
            return 1;
        }
        //ここだけ特別扱い
        if (x == 1 && y == 2)
        {
            return Route2(x - 1, y);
        }
        return (x > 0 ? Route2(x - 1, y) : 0) + (y > 0 ? Route2(x, y - 1) : 0);
    }
}

#!/bin/bash

counts=(1)

while true; do
    # horizontal bars
    read -r line || break
    for ((i = 0; i * 2 + 1 < ${#line}; i++)) {
        [ "${line:$((i*2+1)):1}" = - ] && ((counts[i+1] += counts[i]))
    }

    # vertical bars
    read -r line || break
    for ((i = 0; i * 2 < ${#line}; i++)) {
        [ "${line:$((i*2)):1}" = '|' ] || counts[i]=0
    }
done

echo ${counts[${#counts[@]} - 1]}

inc = lambda c: chr(ord(c) + 1)
edge_from = lambda p, points, deny: \
    [ q for q in [inc(p[0]) + p[1], p[0] + inc(p[1])]
            if q in points and (p, q) not in deny ]
edges = lambda points, deny: \
    dict([(p, [e for e in edge_from(p, points, deny)]) for p in points ])
def count_paths(E, start, goal):
    return 1 if start == goal \
            else sum([count_paths(E, p, goal) for p in E[start]])

points = [ row + col for row in 'ABCDE' for col in '1234' ]
E1 = edges(points, [])
E2 = edges(points, [('B2','C2'), ('C3', 'C4'), ('D2','D3')])
print count_paths(E1, 'A1', 'E4')
print count_paths(E2, 'A1', 'E4')

#include <iostream>
using namespace std;

int main(){
  int road[5][4] = { {0, 1, 1, 1},
                      {2, 3, 3, 3},
                      {2, 1, 3, 3},
                      {2, 3, 3, 3},
                      {2, 3, 3, 3}
                    };

  int pattern[5][4];

  int i, j;
  for(i=0; i<5; i++){
    for(j=0; j<4; j++){
      switch(road[i][j]){
      case 0: pattern[i][j] = 1; break;
      case 1: pattern[i][j] = pattern[i][j-1]; break;
      case 2: pattern[i][j] = pattern[i-1][j]; break;
      case 3: pattern[i][j] = pattern[i][j-1] + pattern[i-1][j]; break;
      }
    }
  }
  cout << "road pattern is " << pattern[4][3] << ".\n";

  return 0;
}

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Sample221 {
    static class RouteNode {
        public final List<RouteNode> dests = new ArrayList<RouteNode>();
        public int routeCount = 0;
    }

    private final Map<Integer, Map<Integer, RouteNode>> nodeMap_
        = new HashMap<Integer, Map<Integer,RouteNode>>();
    private RouteNode startNode_;
    private RouteNode goalNode_;

    public int countRoute(String[] map) {
        createNode(map);

        Set<RouteNode> checkNodes = new HashSet<RouteNode>();
        checkNodes.add(startNode_);
        startNode_.routeCount = 1;
        while (!(checkNodes.isEmpty() || goalNode_.routeCount > 0)) {
            checkNodes = checkNextNode(checkNodes);
        }
        return goalNode_.routeCount;
    }

    private Set<RouteNode> checkNextNode(Set<RouteNode> nodes) {
        Set<RouteNode> nextNodes = new HashSet<RouteNode>();
        for (RouteNode node: nodes) {
            for (RouteNode next: node.dests) {
                next.routeCount += node.routeCount;
                nextNodes.add(next);
            }
        }
        return nextNodes;
    }

    private void createNode(String[] map) {
        createNodeInstance(map);
        createLinkNode(map);
    }
    private void createNodeInstance(String[] map) {
        for (int row = 0, rowMax = (map.length + 1) / 2; row < rowMax; row++) {
            for (int col = 0, colMax = (map[row * 2].length() + 1) / 2; col < colMax; col++) {
                Map<Integer, RouteNode> rowMap = nodeMap_.get(row);
                if (rowMap == null) {
                    rowMap = new HashMap<Integer, RouteNode>();
                    nodeMap_.put(row, rowMap);
                }
                RouteNode node = new RouteNode();
                rowMap.put(col, node);
                char c = map[row * 2].charAt(col * 2);
                if (c == 'P') startNode_ = node;
                if (c == 'Q') goalNode_ = node;
            }
        }
    }
    private void createLinkNode(String[] map) {
        for (int row = 0; row < map.length; row++) {
            for (int col = 0; col < map[row].length(); col++) {
                switch (row % 2 * 2 + col % 2) {
                    case 0:    // Node
                        break;
                    case 1: // horizontal route
                        char h = map[row].charAt(col);
                        if (h == '-') {
                            int linkRow = row / 2;
                            int linkCol = col / 2;
                            linkNode(linkRow, linkCol, linkRow, linkCol + 1);
                        }
                        break;
                    case 2: // vertical route
                        char v = map[row].charAt(col);
                        if (v == '|') {
                            int linkRow = row / 2;
                            int linkCol = col / 2;
                            linkNode(linkRow, linkCol, linkRow + 1, linkCol);
                        }
                        break;
                    case 3: // blank
                        break;
                }
            }
        }
    }
    private void linkNode(int fromRow, int fromCol, int toRow, int toCol) {
        RouteNode fromNode = nodeMap_.get(fromRow).get(fromCol);
        RouteNode toNode = nodeMap_.get(toRow).get(toCol);
        fromNode.dests.add(toNode);
    }


    public static void main(String[] args) {
        Sample221 sample = new Sample221();
        String[] ex1 = new String[] {
                "P-+-+-+",
                "| | | |",
                "+-+-+-+",
                "| | | |",
                "+-+-+-+",
                "| | | |",
                "+-+-+-+",
                "| | | |",
                "+-+-+-Q",
        };
        System.out.println(sample.countRoute(ex1));

        String[] ex2 = new String[] {
                "P-+-+-+",
                "| | | |",
                "+-+-+-+",
                "|   | |",
                "+-+-+ +",
                "| | | |",
                "+-+ +-+",
                "| | | |",
                "+-+-+-Q",
        };
        System.out.println(sample.countRoute(ex2));
    }
}

| width map counts index |

width := 4.
map := 
    'P-+-+-+',
    '| | | |',
    '+-+-+-+',
    '|   | |',
    '+-+-+ +',
    '| | | |',
    '+-+ +-+',
    '| | | |',
    '+-+-+-Q'.

counts := Array new: width withAll: 0.
counts at: 1 put: 1.
index := 1.
(2 to: map size by: 2) do: [:pos |
    index := index + 1.
    (map at: pos) caseOf: {
        [$-] -> [counts at: (index - 1 \\ width + 1) incrementBy: (counts atWrap: index - 1)].
        [$ ] -> [index > width ifTrue: [counts atWrap: index put: 0]]} otherwise: [].
    index = (width * 2) ifTrue: [index := 1]].
counts last   "=> 15 "

def sum(a)
  a.inject(0){|r,e|r+e}
end

map = [0]*3+[1]*4
path1 = map.permutation.to_a.uniq
path2 = path1.reject{|pt|
  sum(pt[0,2])==1 && pt[2]==1 ||
  sum(pt[0,4])==2 && pt[4]==0 ||
  sum(pt[0,4])==3 && pt[4]==0
}

p path1.size, path2.size

type Counter    = Int -> Int            -- 経路数をカウントする関数
type Grid       = Counter               -- 格子点はカウンタで表現
type Connection                         -- 接続情報は
     =  Grid                            --   上側格子点と
     -> Grid                            --   左側格子点とを引数とし
     -> Grid                            --   当該格子点を返す関数で表現

grids :: [[Connection]] -> [[Grid]]
grids = tail . scanl acc (repeat id)
  where 
    acc fs = tail . scanl (flip ($)) id . zipWith (flip ($)) fs

endpoint :: [[Grid]] -> Grid
endpoint = last . last

count :: Grid -> Int
count = ($ 1)

answer1 = (count . endpoint . grids) sample1
answer2 = (count . endpoint . grids) sample2

-- 格子点の接続情報

(&&&) :: (a -> b) -> (a -> c) -> (a -> (b,c))
(f &&& g) x = (f x, g x)

s,n,u,l,b :: Connection
s _     _    = id                              -- スタート地点
n _     _    = const 0                         -- 左からも、上からも経路がない
u upper _    = upper                           -- 上からの経路のみ
l _     left = left                            -- 左からの経路のみ
b upper left = uncurry (+) . (upper &&& left)  -- 左からも、上からも経路あり

-- 経路情報

sample1, sample2 :: [[Connection]]
sample1 = [[s,l,l,l]
          ,[u,b,b,b]
          ,[u,b,b,b]
          ,[u,b,b,b]
          ,[u,b,b,b]]

sample2 = [[s,l,l,l]
          ,[u,b,b,b]
          ,[u,l,b,u]
          ,[u,b,u,b]
          ,[u,b,b,b]]

#順列してuniqする。
pq = [:-,:-,:-,:|,:|,:|,:|].permutation.to_a.uniq

#図1 
p pq.size

#図2 配列の配列の3番目が|であるものを削除して.size。
p pq.delete_if{|i|i[2] == :|}.size

// 各点での経路の数
template<char CHAR, template<int, int> class MAP, int ROW, int COL> struct C { static const int value = 0; };

// 経路を計算するテンプレート
template<template<int, int> class MAP, int ROW, int COL> struct Count { static const int value = C<MAP<ROW, COL>::value, MAP, ROW, COL>::value; };

// 各点での経路の数: キャラクタごとに特殊化
template<template<int, int> class MAP, int ROW, int COL> struct C<'s', MAP, ROW, COL> { static const int value = 1; };
template<template<int, int> class MAP, int ROW, int COL> struct C<'l', MAP, ROW, COL> { static const int value = Count<MAP, ROW, COL - 1>::value; };
template<template<int, int> class MAP, int ROW, int COL> struct C<'u', MAP, ROW, COL> { static const int value = Count<MAP, ROW - 1, COL>::value; };
template<template<int, int> class MAP, int ROW, int COL> struct C<'b', MAP, ROW, COL> { static const int value = Count<MAP, ROW - 1, COL>::value + Count<MAP, ROW, COL - 1>::value; };

// 問1の図を定義するテンプレート
template<int ROW, int COL> struct Map1         { static const char value = 'b'; }; // 基本的には左、上とも通れる
template<int COL>          struct Map1<0, COL> { static const char value = 'l'; }; // 0行目は基本的に左だけ通れる
template<int ROW>          struct Map1<ROW, 0> { static const char value = 'u'; }; // 0桁目は基本的に上だけ通れる
template<>                 struct Map1<0, 0>   { static const char value = 's'; }; // 0行0桁目は起点

// 問2の図を定義するテンプレート
template<int ROW, int COL> struct Map2         { static const char value = 'b'; }; // 基本的には左、上とも通れる
template<int COL>          struct Map2<0, COL> { static const char value = 'l'; }; // 0行目は基本的に左だけ通れる
template<int ROW>          struct Map2<ROW, 0> { static const char value = 'u'; }; // 0桁目は基本的に上だけ通れる
template<>                 struct Map2<0, 0>   { static const char value = 's'; }; // 0行0桁目は起点
template<>                 struct Map2<2, 1>   { static const char value = 'l'; }; // 2行1桁目は左だけ通れる
template<>                 struct Map2<2, 3>   { static const char value = 'u'; }; // 2行3桁目は上だけ通れる
template<>                 struct Map2<3, 2>   { static const char value = 'u'; }; // 3行2桁目は上だけ通れる

#include <iostream>

int main(int, char* [])
{
    std::cout << "問1の答えは " << Count<Map1, 4, 3>::value << " 通りです" << std::endl;
    std::cout << "問2の答えは " << Count<Map2, 4, 3>::value << " 通りです" << std::endl;

    return 0;
}

#include <stdio.h>
#include <stdlib.h>

#define HEIGHT 5
#define WIDTH 4
typedef enum tagLoad
{
    NONE,
    RIGHT,
    UNDER,
    BOTH
} Load;

Load map1[HEIGHT][WIDTH] = {
    {BOTH, BOTH, BOTH, UNDER},
    {BOTH, BOTH, BOTH, UNDER},
    {BOTH, BOTH, BOTH, UNDER},
    {BOTH, BOTH, BOTH, UNDER},
    {RIGHT, RIGHT, RIGHT, NONE}
};

Load map2[HEIGHT][WIDTH] = {
    {BOTH, BOTH, BOTH, UNDER},
    {BOTH, RIGHT, BOTH, UNDER},
    {BOTH, BOTH, UNDER, UNDER},
    {BOTH, UNDER, BOTH, UNDER},
    {RIGHT, RIGHT, RIGHT, NONE}
};

void search(Load map[HEIGHT][WIDTH], int y, int x, int* count)
{
    if(y == HEIGHT-1)
    {
        (*count)++;
        return;
    }
    switch(map[y][x])
    {
    case RIGHT:
        search(map, y, x+1, count);
        break;
    case UNDER:
        search(map, y+1, x, count);
        break;
    case BOTH:
        search(map, y+1, x, count);
        search(map, y, x+1, count);
        break;
    }
}

int main(void)
{
    int count = 0;
    search(map1, 0, 0, &count);
    printf("map1: %d\n", count);
    count = 0;
    search(map2, 0, 0, &count);
    printf("map2: %d\n", count);
    return EXIT_SUCCESS;
}

!PS

% Ans 1   サイズのみから (1)のみ計算
/fact { dup 1 gt { dup 1 sub fact mul } if } def
/CountPath1 { 2 copy add fact exch fact idiv exch fact idiv } def

% Ans 2   (2) 
/CountPath {
    [ 1 index 1 get length {1} repeat ] exch
    {
        dup length 0 1 3 -1 roll 1 sub {
            2 copy get
            dup 2 and 0 eq { 0 } { 3 index 2 index get } ifelse
            exch 1 and 0 ne { 3 index 2 index 1 sub get add } if
            3 index 3 1 roll put
        } for
        pop
    } forall
    dup length 1 sub get
} def

% === Test ===
% 1:左に繋がる 2:上に繋がる 3:両方に繋がる
/Map1 [
    [ 2 1 1 1 ]
    [ 2 3 3 3 ]
    [ 2 3 3 3 ]
    [ 2 3 3 3 ]
    [ 2 3 3 3 ]
] def

/Map2 [
    [ 2 1 1 1 ]
    [ 2 3 3 3 ]
    [ 2 1 3 2 ]
    [ 2 3 2 3 ]
    [ 2 3 3 3 ]
] def

3 4 CountPath1 =
Map1 CountPath =
Map2 CountPath =

function Point(up, left) {
   this.up = up; this.left =left;
}
Point.U = new Point(true, false);
Point.L = new Point(false, true);
Point.UL = new Point(true, true);
Point.NON = new Point(false, false);

var points;
with(Point) {
   points = [
      [U, L,  L,  L],
      [U, UL, UL, UL],
      [U, L,  UL, U],
      [U, UL, U,  UL],
      [U, UL, UL, UL]
   ];
}
function countRoute(points) {
   var count_table = new Array(points[0].lenth);
   count_table[0] = 1;

   for (var i=0, n=points.length; i<n; i++) {
      var row = points[i];
      for (var j=0, m=row.length; j<m; j++) {
         var p = row[j];
         count_table[j] = (p.up && count_table[j] || 0) + (p.left && count_table[j-1] || 0);
      }
   }
   return count_table[count_table.length-1];
}
alert(countRoute(points));

// 図.1
println inspect('''\
P-+-+-+
| | | |
+-+-+-+
| | | |
+-+-+-+
| | | |
+-+-+-+
| | | |
+-+-+-Q''')

// 図.2
println inspect('''\
P-+-+-+
| | | |
+-+-+-+
|   | |
+-+-+ +
| | | |
+-+ +-+
| | | |
+-+-+-Q''')

// 解析
int inspect(String fig) {
  def figure = fig.readLines()

  Point.MAP.clear()
  def pqMap = [:]
  def getPoint = { at -> return Point.MAP.get(at, new Point()) }

  XY.RANGE_Y = 0..<figure.size()
  XY.RANGE_X = 0..<(figure*.size().unique().head())

  // 図形を解析
  figure.eachWithIndex{ line, i ->
    line.eachWithIndex{ str, j ->
      def xy = new XY('y':i, 'x':j)
      Point point

      switch (str) {
        case 'P':
          point = getPoint(xy.toCoordinate())
          pqMap['P'] = [point, xy]
          break
        case 'Q':
          point = getPoint(xy.toCoordinate())
          pqMap['Q'] = [point, xy]
          break
        case '+':
          point = getPoint(xy.toCoordinate())
          break
      }

      if (point) {
        // 上方向
        if (xy.up().toCoordinate()) {
          if (figure[xy.up().y][xy.up().x] == '|') {
            point.ref['U'] = getPoint(xy.up(2).toCoordinate())
          }
        }
        // 下方向
        if (xy.down().toCoordinate()) {
          if (figure[xy.down().y][xy.down().x] == '|') {
            point.ref['D'] = getPoint(xy.down(2).toCoordinate())
          }
        }
        // 左方向
        if (xy.left().toCoordinate()) {
          if (figure[xy.left().y][xy.left().x] == '-') {
            point.ref['L'] = getPoint(xy.left(2).toCoordinate())
          }
        }
        // 右方向
        if (xy.right().toCoordinate()) {
          if (figure[xy.right().y][xy.right().x] == '-') {
            point.ref['R'] = getPoint(xy.right(2).toCoordinate())
          }
        }
      }
    }
  }

  // 方向を設定
  Point.setDirection(pqMap)

  // Qまでのルート数を返却
  return pqMap['Q'][0].getRoot()
}

// 点を表現するクラス
class Point {
  static def DIRECTION = []
  static def MAP = [:]
  def ref = [:]
  def getRoot() {
    def refs = MAP.values().findAll{
      it.ref.findAll{ DIRECTION.contains(it.key) }.values().any{ it == this }
    }
    return refs ? refs.collect{ it.getRoot() }.sum() : 1
  }
  static void setDirection(pqMap) {
    DIRECTION.clear()
    switch (pqMap['P'][1].x - pqMap['Q'][1].x) {
      case {it < 0} : Point.DIRECTION << 'R'; break
      case {it > 0} : Point.DIRECTION << 'L'; break
    }
    switch (pqMap['P'][1].y - pqMap['Q'][1].y) {
      case {it < 0} : Point.DIRECTION << 'D'; break
      case {it > 0} : Point.DIRECTION << 'U'; break
    }
  }
}

// XY座標を表現するクラス
class XY {
  static def RANGE_X, RANGE_Y
  int x, y
  final def closMove = { dx, dy, x, y -> return new XY('x':x + dx, 'y':y + dy) }
  final def closU = closMove.curry( 0, -1)
  final def closD = closMove.curry( 0,  1)
  final def closL = closMove.curry(-1,  0)
  final def closR = closMove.curry( 1,  0)
  def up(count = 1)   { def next = this; count.times{ next = closU(next.x, next.y) }; return next }
  def down(count = 1) { def next = this; count.times{ next = closD(next.x, next.y) }; return next }
  def left(count = 1) { def next = this; count.times{ next = closL(next.x, next.y) }; return next }
  def right(count = 1){ def next = this; count.times{ next = closR(next.x, next.y) }; return next }
  def toCoordinate() {
    if (!RANGE_X.contains(x)) return null
    if (!RANGE_Y.contains(y)) return null
    return "$x,$y" as String
  }
}

(use srfi-1)
(define (problem221 h v . forbidden-routes)
  (define (out-of-route? x y) (or (> x h) (> y v)))
  (define (possible-routes x y)
    (define forbidden (let ((entry (assoc (cons x y) forbidden-routes)))
                        (if entry (cdr entry) '())))
    (filter (lambda (pos) (not (member pos forbidden)))
            (list (cons (+ x 1) y) (cons x (+ y 1)))))
  (define ans-alist (list (cons (cons h (- v 1)) 1) (cons (cons (- h 1) v) 1)))
  (define (problem221-1 x y)
    (if (out-of-route? x y) 0
        (let ((entry (assoc (cons x y) ans-alist)))
          (if entry (cdr entry)
              (let ((ans
                     (apply + (map (lambda (pos) (problem221-1 (car pos) (cdr pos)))
                                   (possible-routes x y)))))
                (set! ans-alist (cons (cons (cons x y) ans) ans-alist))
                ans)))))
  (problem221-1 0 0))
(display "problem 1: ")
(display (problem221 3 4))
(newline)
(display "problem 2: ")
(display (problem221 3 4
                     '((1 . 1) . ((1 . 2)))
                     '((2 . 2) . ((3 . 2)))
                     '((1 . 3) . ((2 . 3)))))
(newline)

def x = 3
def y = 4
def LEFT = 0
def DOWN = 1

def list = []
(x+y).times{
    list << [LEFT, DOWN]
}
def all = list.combinations().unique().findAll{ it.count(LEFT) == x }
def part = all.findAll{
    !(it[0..1].count(LEFT) == 1 && it[2] == DOWN)
}.findAll{
    !(it[0..3].count(LEFT) == 1 && it[4] == LEFT)
}.findAll{
    !(it[0..3].count(LEFT) == 2 && it[4] == LEFT)
}
println all.size()
println part.size()

$goal="Q";
$pipe[0]="-";
$pipe[1]="|";
#route=1;
#hier=0;
#houkou=0;

    gofiletop;
    while( 1==1 ) {
        if( #houkou==0 || #houkou==1 ) {
            call rightdown #houkou;
            #ret=##return;
            if( #ret==1 ) {
                #rd[#hier]=#houkou;
                #pnt[#hier]=#pnt[#hier]+1;
                #hier=#hier+1;
                #houkou=0;
                continue;
            }
            #houkou=#houkou+1;
        } else {
            if( char(code)!=$goal ) {
                #route = #route+#pnt[#hier]-1;
            }
            #pnt[#hier]=0;
            #hier=#hier-1;
            #houkou=#rd[#hier]+1;
            if( #hier==-1 ) break;
            call gowhere #rd[#hier]+2;
            call gowhere #rd[#hier]+2;
            continue;
        }
    }
    message( str(#route) );
    endmacro;

rightdown:
    call gowhere ##1;
    if( char(code)==$pipe[##1] ) {
        call gowhere ##1;
        return 1;
    }
    call gowhere ##1+2;
    return 0;

gowhere:
    if( ##1==0 ) right;
    if( ##1==1 ) down;
    if( ##1==2 ) left;
    if( ##1==3 ) up;
    return;

pat =: (1:`($:@:+&0 _1)`($:@:+&_1 0)`($:@:+&0 _1+$:@:+&_1 0)@.({&MAP@<)) M.

#! /usr/bin/perl

sub count_path($) {
    my    ($map) = @_;
    my    $count = 0;
    if (scalar(@$map) == 1 && scalar(@{$map->[0]}) == 1) {
        $count = 1;
    } else {
        my    $current = $map->[0]->[0];
        my    $temp = [];
        if (substr($current, 1, 1) ne ' ') {
            @$temp = map({ my @t = @$_[1..$#$_]; \@t; } @$map);
            $count += count_path($temp);
        }
        if (substr($current, 0, 1) ne ' ') {
            @$temp = @$map[1..$#$map];
            $count += count_path($temp);
        }
    }
    $count;
}

print count_path([
        ['|-','|-','|-','| '],
        ['|-','|-','|-','| '],
        ['|-','|-','|-','| '],
        ['|-','|-','|-','| '],
        [' -',' -',' -','  ']
    ]) . "\n";
print count_path([
        ['|-','|-','|-','| '],
        ['|-',' -','|-','| '],
        ['|-','|-','| ','| '],
        ['|-','| ','|-','| '],
        [' -',' -',' -','  ']
    ]) . "\n";

object CountPath {
    def countPath(m:List[List[Int]]):Int = m.flatten[Int].size match {
            case 1 => 1
            case _ => m.first.first match {
                case 3 => countPath(m.tail) + countPath(m.map(l => l.tail))
                case 2 => countPath(m.tail)
                case 1 => countPath(m.map(l => l.tail))
                case _ => 0
            }
        }
    def main(args:Array[String]):Unit = {
        println(countPath(List(
                List(3,3,3,2),
                List(3,3,3,2),
                List(3,3,3,2),
                List(3,3,3,2),
                List(1,1,1,0)
            )))
        println(countPath(List(
                List(3,3,3,2),
                List(3,1,3,2),
                List(3,3,2,2),
                List(3,2,3,2),
                List(1,1,1,0)
            )))
    }
}

$road = {{0,1,1,1}, {2,3,3,3}, {2,1,3,3}, {2,3,3,3}, {2,3,3,3}};
for($i = 0; $i < 5; ++$i) {
    for($j = 0; $j < 4; ++$j) {
        if( $road[$i][$j] == 0 ) $n[$i][$j] = 1;
        else if( $road[$i][$j] == 1 ) $n[$i][$j] = $n[$i][$j-1];
        else if( $road[$i][$j] == 2 ) $n[$i][$j] = $n[$i-1][$j];
        else if( $road[$i][$j] == 3 ) $n[$i][$j] = $n[$i][$j-1] + $n[$i-1][$j];
    }
}
cout << $n[4][3] << "\n";

package 
{
    import flash.display.Sprite;
    import flash.events.Event;
    import flash.events.MouseEvent;
    import flash.geom.Point;
    import flash.text.TextField;
    import flash.text.TextFieldAutoSize;
    
    [SWF(width=465, height=465, frameRate=30, backgroundColor="#ffffff")]
    
    /**
     * via http://ja.doukaku.org/221/
     * 左上の点から右下の点までいくのに何通りの経路があるかを数えて、左上に表示します。
     *  定数になっている、X_COUNT と Y_COUNT の値を変更すると経路の数が変更できます。
     * 経路上の線をクリックすると、通行止めにできます。その時経路の数も変更されます。
     */
    public class CountPath extends Sprite 
    {
        public static const X_COUNT:int = 3;
        public static const Y_COUNT:int = 4;
        
        public static const OFFSET:Point = new Point(40, 20);
        
        private var answer:TextField = new TextField();
        private var nodeMap:Array = new Array();
        
        public function CountPath() {
            if (stage) init();
            else addEventListener(Event.ADDED_TO_STAGE, init);
        }
        
        private function init(e:Event = null):void {
            removeEventListener(Event.ADDED_TO_STAGE, init);
            
            var maxCount:int = (X_COUNT > Y_COUNT)? X_COUNT: Y_COUNT;
            var scale:Number = 420.0 / maxCount;
            var offset:Point = new Point(OFFSET.x, OFFSET.y);
            
            offset.x += Number(maxCount - X_COUNT) * scale / 2;
            offset.y += Number(maxCount - Y_COUNT) * scale / 2;
            
            for (var y:int = 0; y <= Y_COUNT; y++) {
                nodeMap[y] = new Array();
                for (var x:int = 0; x <= X_COUNT; x++) {
                    var node:Node = new Node(x, y);
                    node.draw(this.graphics, scale, offset);
                    nodeMap[y][x] = node;
                    if (y > 0) {
                        var yEdge:Edge = new Edge(nodeMap[y - 1][x], nodeMap[y][x]);
                        yEdge.draw(scale, offset);
                        addChild(yEdge);
                    }
                    if (x > 0) {
                        var xEdge:Edge = new Edge(nodeMap[y][x - 1], nodeMap[y][x]);
                        xEdge.draw(scale, offset);
                        addChild(xEdge);
                    }
                }
            }
            
            answer.autoSize = TextFieldAutoSize.LEFT;
            answer.x = 10;
            answer.y = 10;
            addChild(answer);
            
            displayCount();
            this.addEventListener(MouseEvent.CLICK, function(event:MouseEvent):void {
                displayCount();
            });
        }
        
        public function displayCount():void {
            answer.text = String(calcRouteCount());
        }
        
        public function calcRouteCount():int {
            clearCount();
            var startNode:Node = nodeMap[0][0];
            var endNode:Node = nodeMap[Y_COUNT][X_COUNT];
            
            startNode.nodeCount = 1;
            calcCount(startNode);
            return endNode.nodeCount;
        }
        private function calcCount(start:Node):void {
            for each(var edge:Edge in start.getEdges()) {
                if (edge.passable) {
                    var node:Node = edge.end;
                    node.nodeCount += start.nodeCount;
                    calcCount(node);
                }
            }
        }
        
        private function clearCount():void {
            for each(var array:Array in nodeMap) {
                for each (var node:Node in array) {
                    node.nodeCount = 0;
                }
            }
        }
    }
}

import flash.display.Graphics;
import flash.display.Sprite
import flash.events.MouseEvent;
import flash.geom.Point;

class Node {
    private var x_:int;
    private var y_:int;
    private var edges:Vector.<Edge> = new Vector.<Edge>();
    private var count:int = 0;
    
    public function Node(x:int, y:int) {
        this.x_ = x;
        this.y_ = y;
    }
    public function get X():int { return this.x_; }
    public function get Y():int { return this.y_; }
    public function getViewX(scale:Number, offset:Point):Number {
        return this.X * scale + offset.x;
    }
    public function getViewY(scale:Number, offset:Point):Number {
        return this.Y * scale + offset.y;
    }
    
    public function get nodeCount():int { return count; }
    public function set nodeCount(count:int):void { this.count = count; }
    
    public function getEdges():Vector.<Edge> {
        return edges;
    }
    public function addEdge(e:Edge):void {
        edges.push(e);
    }
    
    public function draw(g:Graphics, scale:Number, offset:Point):void {
        g.lineStyle();
        g.beginFill(0x000000, 0.9);
        g.drawCircle(getViewX(scale, offset), getViewY(scale, offset), 10);
        g.endFill();
    }
}

class Edge extends Sprite {
    private var startNode:Node;
    private var endNode:Node;
    private var pass:Boolean = true;
    
    public function Edge(start:Node, end:Node) {
        this.startNode = start;
        this.endNode = end;
        this.addEventListener(MouseEvent.CLICK, function(event:MouseEvent):void {
            alpha = 1.0 - alpha;
            pass = !pass;
        });
        this.startNode.addEdge(this);
    }
    public function get start():Node { return this.startNode; }
    public function get end():Node { return this.endNode; }
    public function get passable():Boolean { return this.pass; }
    
    public function draw(scale:Number, offset:Point):void {
        var g:Graphics = this.graphics;
        g.lineStyle(5, 0x000000, 0.8);
        g.moveTo(startNode.getViewX(scale, offset), startNode.getViewY(scale, offset));
        g.lineTo(endNode.getViewX(scale, offset), endNode.getViewY(scale, offset));
        this.alpha = 0.8;
    }
}

module Main where

main = interact $ show.count.lines

count ["Q"]                     = 1
count xss@((_:'-':_):('|':_):_) = count (map (drop 2) xss) + count (drop 2 xss)
count xss@((_:'-':_):_)         = count (map (drop 2) xss)
count xss@(_:('|':_):_)         = count (drop 2 xss)
count _                         = 0