取暖管道

取暖管道

测试数据来自 wjszez/1551

【问题描述】
一块矩形土地被分为N*M的单位正方形,现在要在这块土地埋设取暖管道,管道将从坐标为(1,1)小块(左上角,上部边缘)延伸到(N,M)(右下角,右部边缘). 共有4种管道可选,如图所示.

每种管道将占据一个单位正方形土地.而且管道不能旋转.显而易见,要构成一个管道系统,我们必须保证管道是连续贯通的.
一开始,在地图上标出了已经埋设好的管道.在铺设管道系统时可以利用这些管道,但不能把它们移开铺设新管道;同时,标有树木的方格表示这里是花园,地下不能埋设管道.
下图表示一个4*5的地区,(4,2)处有一个花园.

有三种不同的铺设方法,如图:

下面请你写一个程序,对一个给定的地图,找出有多少种不同的铺设方案.

【输入格式】
第一行为两个整数N和 M(都不超过10),接下来的M行,每行有N个整数,表示地图中的每一小格.其中1-4依次表示图中四种管道,5表示花园,0表示空地.

【输出格式】
单个整数,表示不同方法数.

【输入样例】
TRASE.IN
4 5
0 0 3 2
0 4 0 5
4 0 0 0
4 0 1 0
0 3 0 0

【输出样例】
TRASE.OUT
3

信息

ID
1963
难度
(无)
分类
(无)
标签
递交数
0
已通过
0
通过率
?
上传者