← 返回题目列表

AtCoder · joi2010yo_f

F. 没有方向感的驯鹿

中文机器翻译题面 查看原题

配点: 100 点

問題

圣诞老人今年再次从天而降JOI小镇。 JOI镇的每家每户都有一个孩子,所以这位圣诞老人要给JOI镇的每家每户分发礼物。不过,今年和我在一起的驯鹿有点缺乏方向感,除了楼顶我下不了任何地方,所以我想我得设计一条稍微好一点的路线,才能给各家各户分发礼物。

JOI Town分为北、南、东、西,每个街区要么是房屋,要么是教堂,要么是空地。在JOI镇 1 只有一座教堂。根据以下规则,圣诞老人和他的驯鹿从教堂出发,拜访各家各户。 1 每次分发完礼物后,返回教堂。

  • 今年的驯鹿有一点方向感,所以它们只能向北、南、东、西直线飞行,不能在空中改变方向。
  • 尚未发放礼物的房屋可以自由通过。你可以去任何还没有分发礼物的房子。当他们到达一户人家时,他们总是分发礼物,然后向北、向南、向东、向西飞去。
  • JOI 在镇上的家里,圣诞夜是在圣诞老人到来之前不打开壁炉的,但在圣诞老人飞走后,壁炉就会打开。如果你打开壁炉,烟就会从烟囱里冒出来,所以你不能经过分发礼物的房子。
  • 你可以自由地通过教堂上方。不过,由于教堂正在举行礼拜,所以在所有的礼物都分发完之前我不能去教堂。
  • 你可以自由地通过空地,但你不能下降到空地上。

给定一个城镇的结构作为输入,编写一个程序来查找圣诞老人和他的驯鹿分发礼物可以采取的路线数量。


入力

输入是 有一行 n + 1 。1 行是一个整数 m (1 \leqq m \leqq 10) 和整数 n (1 \leqq n \leqq 10) 用空格分隔。 在2 从行 n + 1 行之前的每一行中,0, 1, 2 ,以空格分隔。 写入 m ,分别代表各部分的状态。从北方 i ,从西边 j 第分区(i,j) 如果我们把它写成 (1 \leqq i \leqq n,1 \leqq j \leqq m) ,第 i + 1 线 第 j 个值是分区 如果 (i, j) 是一块空地, 0 ,如果是房子,那么 1 ,如果是教堂,那么 2 变为。教堂数量 1 房屋数量为 1 以上 23 下面。然而,在用于评分的输入数据中,要分布的方向是 2\,000\,000 切勿过马路。

出力

输出仅包含一个整数,表示分发礼物的方式有多少种。 由 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

入力例 <var>2</var> に対する <var>6</var> 通り全ての道順(数字は配る順序を表す)