第９回日本情報オリンピック　予選６

2009年12月13日
情報オリンピック日本委員会

問題

今年も JOI 町にサンタクロースが空からやってきた．JOI 町にある全ての家には子供がいるので，このサンタクロースは JOI 町の全ての家にプレゼントを配ってまわらなければならない．しかし，今年は連れているトナカイが少々方向音痴であり，また建物の上以外に降りることができないため，全ての家にプレゼントを配るためには少々道順を工夫しなければならないようだ．

JOI 町は東西南北に区画整理されており，各区画は家，教会，空き地のいずれかである．JOI 町には 1 つだけ教会がある．次のルールに従い，サンタクロースとトナカイは教会から出発し，全ての家に 1 回ずつプレゼントを配った後，教会に戻る．

• 今年のトナカイは少々方向音痴であるため，東西南北いずれかの方向にまっすぐ飛ぶことしかできず，空中では方向転換できない．
• まだプレゼントを配っていない家の上は自由に通過できる．まだプレゼントを配っていない家には降りることができる．家に降りた時は必ずプレゼントを配り，その後は東西南北いずれかの方向に飛び立つ．
• JOI 町の家では，クリスマスの夜はサンタクロースが来るまでは暖炉をつけずに過ごしているが，サンタクロースが飛び立った後は暖炉をつける．暖炉をつけると煙突から煙が出るので，プレゼントを配り終えた家の上を通過することはできない．
• 教会の上は自由に通過することができる．しかし，教会では礼拝が行われているので，全てのプレゼントを配り終えるまで教会に降りることはできない．
• 空き地の上は自由に通過することができるが，空き地に降りることはできない．

入力として町の構造が与えられたとき，サンタクロースとトナカイがプレゼントを配る道順が何通りあるかを求めるプログラムを作成せよ．

入力

入力は n+1 行ある． 1 行目には整数 m (1 ≦ m ≦ 10) と整数 n (1 ≦ n ≦ 10) が空白で区切られて書かれている． 2 行目から n+1 行目までの各行には，0，1，2 のいずれかが， 空白で区切られて m 個書かれており，各々が各区画の状態を表している． 北から i 番目，西から j 番目の区画を (i,j) と記述することにすると (1 ≦ i ≦ n, 1 ≦ j ≦ m)， 第 i+1 行目の j 番目の値は， 区画 (i,j) が空き地である場合は 0 となり， 家である場合は 1 となり， 教会である場合は 2 となる． 教会の個数は 1 であり，家の個数は 1 以上 23 以下である． ただし，採点用入力データでは配る道順が 2000000 通りをこえることはない．

出力

出力はプレゼントを配る道順が何通りあるかを表す整数のみを含む 1 行からなる．

入出力例

入力例 1 3 2 1 0 1 1 0 2 　 出力例 1 2 入力例 2 3 3 1 1 1 1 0 1 1 1 2 　 出力例 2 6

図: 入力例 2 に対する 6 通り全ての道順 （数字は配る順序を表す）

※各入出力例のデータは， 右クリック等によりファイルに保存して利用可能です．

採点用データ