最短経路の個数を数える問題である． 同様の問題を数学の授業でやったことのある人も多いだろう． 『計算の仕方は分かったが，うまくプログラムが書けなかった』 という人も多かったのではないだろうか．

　この問題の効率の良い解法は次のようなものである． 交差点 (1,1) から出発して，東または北にのみ向かって移動し， 交差点 (j,k) に移動する方法を t[j][k] 通りとおく． 以下では簡単のため， j,k は 0 ≦ j ≦ a, 0 ≦ k ≦ b の範囲であるとし， j または k が 0 のときは t[j][k] = 0 とおく． このとき， t[j][k] は次の漸化式をみたす．

• (1,1) が工事中でないとき : t[1][1] = 1
• j または k が 0 のとき : t[j][k] = 0
• 交差点 (j,k) が工事中のとき : t[j][k] = 0
• そうでないとき : t[j][k] = t[j-1][k] + t[j][k-1]

　この漸化式を用いて t[a][b] を求めればよい．

解法1 　2重ループを使って，t[j][k] を j,k が小さい方から順に計算する．具体的には，

• 配列 t[j][k] (0 ≦ j ≦ a, 0 ≦ k ≦ b) を全て0に初期化する．
• j を 1 から a まで動かす．
  • k を 1 から b まで動かす．
    • (j,k) = (1,1) であり，さらに (1,1) が工事中でないとき : t[j][k] = 1
    • (j,k) が工事中のとき : t[j][k] = 0
    • そうでないとき : t[j][k] = t[j-1][k] + t[j][k-1]

により，配列 t[j][k] が全て計算できる．その後，t[a][b] を出力する．

解法2 　関数の中で自分自身を呼び出す「再帰」のテクニックを使ってもよい． 次のような関数 func(j,k) を用意し，func(a,b) を出力する．

　　func(j,k)
　　{
　　　j または k が 0 のときは 0 を返す．
　　　(j,k) が工事中の時は 0 を返す．
　　　(j,k) = (1,1) なら 1 を返す．
　　　そうでないときは， func(j-1,k) + func(j,k-1) を返す．
　　}

　なお，この関数 func(j,k) は， このままでは同じ (j,k) に関する計算を2回以上行う可能性があるため，効率が悪い． 一度計算した結果を記憶領域に格納しておき，二度目以降はそれを参照する， という工夫によって高速化することもできる．

　漸化式の問題を「再帰」を使って解く利点の一つは， 再帰呼び出しの過程で， 目的地 (a,b) に到達する可能性のある t[j][k] だけが計算されることにある (一方，上に述べた2重ループの方法では，全ての t[j][k] を計算することになるので， 無駄な計算が含まれてしまう)． 「再帰」は，うまく使うと短い行数のプログラムで効率よく計算することができる強力なテクニックなので， ぜひこれを機会に使いこなせるようになってほしい．

解法3 　さらに別解として，かなり効率は悪いが， 「全ての経路を列挙して調べる」という解法(全数検査法)もある． プログラム内で _a+b-2C_a-1 通りの経路を全て生成し， 工事中の交差点を通らないものの個数を数えればよい．

　このように，この問題には複数の解法がある． もちろん，それぞれの解法には，短所・長所がある． 今回は，入力データのサイズをかなり小さく設定したので(1 ≦ a,b ≦ 16)， 正しく動作するプログラムさえ書ければ，どのような解法でも満点を取ることは十分に可能である． もちろん，JOI本選やIOIで出題されるような難易度の高い問題では， 問題の状況にあわせて最適なアルゴリズムを考え，プログラムを書くことも必要になってくる． 全数検査法では，データのサイズが大きい場合に制限時間内に答えを出力できずに， 部分点しか得られないこともあるだろう．

　この問題ができた人も，今回はうまくいかなかった人も， ぜひ，上に述べた様々な解法をきちんと理解して， もう一度，自分の手でじっくりとプログラムを書いて解き直してみてほしい． そして，そこで使われる考え方やテクニックをしっかりと身に付けて， より難易度の高い問題にも対応できる実力をつけていってほしい．