P3314 [SDOI2014]电路板

    • 0通过
    • 6提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 2014 山东 高性能
  • 难度 尚无评定
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    对于用户给出的电路图和指定大小的电路板,Alice和Bob需要将电路在电路板上实现出来。

    所谓电路板,可以看作是一个n*m的格子图。 用户给定的电路由若干电路原件组成,每一个电路原件可能会占用一个或多个格子。这里,我们将被电路原件占据的格子分为两类。

    第一类只是纯粹占据了这个格子,之后这个格子不会再被使用,也不会从被占据的位置连出去任何的电路线。这样的格子被我们视作是电路板上的障碍物。

    还有一类格子,我们称为是电路原件的接口,上面虽然被电路原件占用,但是仍有可能从其中连出去一些电路线到其它的电路原件上,从而形成电路。

    对于电路图中一些链接某两个原件的电路线,我们可以指定为电路板上的k个格子对,要求每对格子对之间连一条电路线。 同一个格子可能属于多个格子对(比如一些并联电路)。 任意两条电路线不能相交(但可以连接到同一个有着电路原件的格子中),且电路板上的每一个格子的每一条边都只能经过一条电路线。(所以每一个电路原件的接口上只能接出去最多4条不同的电路线)。然而,每一个不被电路原件占用的格子内却可以经过多条电路 线。

    具体来说:为了保证电路线不相交,可以一条电路线从上边界进入当前格子,从左边界离开这个格子,另外一条电路线可以从下边界进入格子,从右边界出去。(需要注意的是:电路线本身是没有方向感念的,即格子对描述的边关系是无向边。所以这样的方案也可以描述为从左边界进入后从上边界出去,从右边界进入后从下边界出去)相似的方案还有好几种。

    现在,Alice希望找到一个可行方案,使得路径的总长度最短。而Bob则希望知道满足最短长度的方案有多少种。

    输入输出格式

    输入格式:

    第一行三个整数,n,m,k,表示电路板的大小,以及需要连接电路线的格子对个数。

    接下来m行,每行n个整数,为0或1。0代表当前格子可以用,否则表示有障碍,不能使用。

    接下来k行,每行4个整数x1,y1,x2,y2,给出一组格子对,表示对应的电路要连接 的两个格子。格子的行列都从0开始编号,所以0<=x1,x2<n,0<=y1,y2<m。

    本题有多组数据(最多30组),输入文件最后以0 0 0 结束。

    输出格式:

    对于每组数据,输出两个整数,最短电线长度和最短电线长度的方案数。 方案数只需要输出对25619849取余数后的结果。

    如果无解,输出-1 0。

    输入输出样例

    输入样例#1: 复制
    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
    输出样例#1: 复制
    16 96
    12 1

    说明

    样例解释:

    第一组数据:(1,2)与(2,1)之间有4条路径,立刻可以发现,最短路径长度和为16。对于每一种可行方案,任意一条(1,2)与(2,1)之间的路径都可以对应要求的4条路径中的任何一条。而若就形态来说,完全不同的方案有4种,考虑到排列数4!=24,所以总的方案为96种。

    第二组数据:因为有3个障碍点,所以可行路径只有一条。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。