JOI logo
第9回日本情報オリンピック 予選6

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

問題
   方向音痴のトナカイ

問題

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

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

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

入力

入力は 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 通り全ての道順
(数字は配る順序を表す)

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


採点用データ

入力データ 入力1 入力2 入力3 入力4 入力5