[WC1999]迷宫改造
成绩 | 开启时间 | 2014年09月19日 星期五 10:08 | |
折扣 | 0.8 | 折扣时间 | 2014年09月26日 星期五 10:08 |
允许迟交 | 是 | 关闭时间 | 2014年09月26日 星期五 10:08 |
输入文件 | rebuildmaze.in | 输出文件 | rebuildmaze.out |
【题目描述】
【输入格式】
输入文件中的第一行为两个整数N,M(3<=N,M<=20)。
第二行中为一个整数k,表示原迷宫中门的总个数。
第i+2(1<=i<=k)行中为四个整数Xi1,Yi1,Xi2,Yi2,表示第Xi1行第Yi1列的单元与第Xi2行Yi2列的单元之间有一扇门,其中:|Xi1-Yi1|+|Xi2-Yi2|=1。
第k+3行中为一个整数,表示p的值。
第k+3+j(1<=j<=p)行中为四个整数Xj1,Yj1,Xj2,Yj2,分别表示第j个家庭成员出发的起点位置(Xj1,Yj1)和要到达的终点位置(Xj2,Yj2),其中:Xj1<=Xj2,Yj1<=Yj2,(Xj1,Yj1)<>(Xj2,Yj2)。
注意:输入数据中同一行各相邻整数之间用一空格分隔。
【输出格式】
为一个整数,表示你所设计的最佳迷宫中新置的门的个数。
【样例输入】
4 4 5 1 1 1 2 2 1 3 1 2 2 3 2 4 2 4 3 1 4 2 4 3 2 1 4 3 1 2 4 2 3 1 4 4
【样例输出】
4
【题目来源】
WC 1999