#P3604. [Sdoi2014]电路板

    ID: 2811 传统题 3000ms 512MiB 尝试: 19 已通过: 5 难度: 10 上传者: 标签>难度分类省选/NOI-动态规划插头 DP插头连通性编码轮廓状态规范化计数 DP数据结构哈希表滚动数组枚举与搜索排列枚举最优性剪枝CF2900

[Sdoi2014]电路板

[SDOI2014] 电路板

题目描述

Alice 和 Bob 要在一块电路板上实现给定的电路。电路板是一个 n×mn\times m 的网格。电路元件会占用一个或多个格子。被占用的格子分为两类。

  • 障碍格不能使用,电路线不能经过它,也不能在其上连接。
  • 接口格可以作为电路线的端点,用于连接其他电路元件。

给出 kk 对要连接的接口格,每一对都需要一条电路线。同一个接口格可以属于多个接口对,接口对可以重复出现。每个给定的接口对对应的电路线分别计数。

电路线在共边的格子间延伸,跨越一条格边计一单位长度。每条格边最多允许一条电路线经过,因此一个接口格最多连出四条线。两条不同的电路线可以在同一个接口格终止,但不能相交。

在未被元件占用的格子内,只要电路线互不交叉,便可以同时通过多条线。例如一条连接该格子的上边和左边,另一条连接下边和右边。电路线没有方向,调换同一条线的起止方向仍是同一个方案。

求电路线总长度的最小值,以及达到最小值的布线方案数。

输入格式

每组数据第一行有三个整数 n,m,kn,m,k,分别表示电路板的行数、列数和需要布线的接口对数。

接下来 nn 行,每行 mm 个整数 00 或 11。00 表示可用,11 表示障碍格。

接下来 kk 行,每行四个整数 x1,y1,x2,y2x_1,y_1,x_2,y_2,表示需要连接的接口 (x1,y1)(x_1,y_1) 和 (x2,y2)(x_2,y_2)。行、列从 00 编号,0≤x1,x2<n0\le x_1,x_2<n,0≤y1,y2<m0\le y_1,y_2<m。

输入至多包含 3030 组数据,以三个零结束。结束行不属于任何一组数据。

输出格式

每组输出一行两个整数,依次为最小总长度和最优方案数对 2561984925619849 取模的结果。无解时输出 -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,2)(1,2) 和 (2,1)(2,1) 之间必须连四条电路线,最小总长度是 1616。按布线形状区分,有四种最优布线。每种布线的四条路线可以任意分配给输入中的四个接口对,因此共有 4⋅4!=964\cdot4!=96 种方案。

第二组中有三个障碍格,达到最小总长度 1212 的方案只有一种。

数据范围与约定

1≤n,m≤91\le n,m\le9,0≤k≤100\le k\le10。至多 3030 组数据。

若某对接口的两个端点是同一个格子,该组无解,输出 -1 0。接口格最多连出四条线;要求超过四条时也无解。输入中的行列均从 00 开始编号。

原赛题面发布页