#P3604. [Sdoi2014]电路板
[Sdoi2014]电路板
[SDOI2014] 电路板
题目描述
Alice 和 Bob 要在一块电路板上实现给定的电路。电路板是一个 的网格。电路元件会占用一个或多个格子。被占用的格子分为两类。
- 障碍格不能使用,电路线不能经过它,也不能在其上连接。
- 接口格可以作为电路线的端点,用于连接其他电路元件。
给出 对要连接的接口格,每一对都需要一条电路线。同一个接口格可以属于多个接口对,接口对可以重复出现。每个给定的接口对对应的电路线分别计数。
电路线在共边的格子间延伸,跨越一条格边计一单位长度。每条格边最多允许一条电路线经过,因此一个接口格最多连出四条线。两条不同的电路线可以在同一个接口格终止,但不能相交。
在未被元件占用的格子内,只要电路线互不交叉,便可以同时通过多条线。例如一条连接该格子的上边和左边,另一条连接下边和右边。电路线没有方向,调换同一条线的起止方向仍是同一个方案。
求电路线总长度的最小值,以及达到最小值的布线方案数。
输入格式
每组数据第一行有三个整数 ,分别表示电路板的行数、列数和需要布线的接口对数。
接下来 行,每行 个整数 或 。 表示可用, 表示障碍格。
接下来 行,每行四个整数 ,表示需要连接的接口 和 。行、列从 编号,,。
输入至多包含 组数据,以三个零结束。结束行不属于任何一组数据。
输出格式
每组输出一行两个整数,依次为最小总长度和最优方案数对 取模的结果。无解时输出 -1 0。
样例
4 4 4
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
1 2 2 1
2 1 1 2
1 2 2 1
2 1 1 2
4 4 2
0 0 1 1
0 0 0 0
1 0 0 0
0 0 0 0
1 0 2 2
0 0 3 0
0 0 0
16 96
12 1
样例解释
第一组中 和 之间必须连四条电路线,最小总长度是 。按布线形状区分,有四种最优布线。每种布线的四条路线可以任意分配给输入中的四个接口对,因此共有 种方案。
第二组中有三个障碍格,达到最小总长度 的方案只有一种。
数据范围与约定
,。至多 组数据。
若某对接口的两个端点是同一个格子,该组无解,输出 -1 0。接口格最多连出四条线;要求超过四条时也无解。输入中的行列均从 开始编号。