网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
取暖管道
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | trase.in | 输出文件 | trase.out |
【题目描述】
一块矩形土地被分为N*M的单位正方形,现在要在这块土地埋设取暖管道,管道将从坐标为(1,1)小块(左上角,上部边缘)延伸到(N,M)(右下角,右部边缘). 共有4种管道可选,如图所示。
每种管道将占据一个单位正方形土地.而且管道不能旋转.显而易见,要构成一个管道系统,我们必须保证管道是连续贯通的.一开始,在地图上标出了已经埋设好的管道.在铺设管道系统时可以利用这些管道,但不能把它们移开铺设新管道;同时,标有树木的方格表示这里是花园,地下不能埋设管道.下图表示一个4*5的地区,(4,2)处有一个花园。
有三种不同的铺设方法,如图:
下面请你写一个程序,对一个给定的地图,找出有多少种不同的铺设方案。
【输入格式】
第一行为两个整数N和M,接下来的M行,每行有N个整数,表示地图中的每一小格.其中1-4依次表示图中四种管道,5表示花园,0表示空地。
【输出格式】
单个整数,表示不同方法数.由于数据可能很大,只需要输出方法数Mod 99999999的结果。
【样例输入】
4 5 0 0 3 2 0 4 0 5 4 0 0 0 4 0 1 0 0 3 0 0
【样例输出】
3
【提示】
【数据规模】
1 ≤ N,M ≤ 2000
【来源】
这是一道上世纪(20世纪)的老题。。。测试数据来自makazeu@gmail.com