b237: CSAPC'09 迷宮任務
Tags :
Accepted rate : 30人/74人 ( 41% ) [非即時]
評分方式:
Tolerant

最近更新 : 2011-04-12 11:35

Content

在一个 n 乘以 m 大小的迷宫当中,你必须依序执行很多项搬东西的任务。每一个任务都有起始点 A 以及终点 B 。行动的时候如果手上没有搬东西,就不会耗费任何体力,但是如果手上有东西,那么耗费的体力就是以移动「一格」消耗一单位的体力来计算。而所谓移动「一格」是指从目前迷宫中的位置往东、南、西、北四个方向前进一步的长度。有趣的是,经过你的缜密观察,尽管迷宫内部相当复杂,它一定会遵守「右手定则」,也就是说,只要摸着右手边的墙壁不断地往前行走,终究可以踏遍迷宫中的每一块空地,并且连所有空地周围看得到的围墙部分都被你摸过了。聪明的你在执行每一个任务的时候,都会挑选最短路径搬运指定物品。请问执行完所有任务以后你所需要耗费的最少体力总和是多少?

Input

输入的第一行包含三个正整数 n, m, Q 。接下来我们用 n 列(rows)每一列以 m 个字元来表示迷宫。迷宫内部标注 '.' 的部份是空地,标记 '#' 的部份是墙。迷宫最外围一定都是墙壁。接下来有 Q 列分别代表 Q 项任务的起点和终点,每一列包含四个整数 x, y, z, w ,代表每一项任务从 (x, y) 出发,并且在 (z, w) 结束。注意到迷宫的编号方式以左上角为 (0, 0) ,右下角为 (n-1, m-1) 。你可以假设输入的所有座标都会是空地的座标。 迷宫里面不会有2x2的空地出现。 (edit: 11/16 10:17am)

Output

请输出依序执行完所有任务后所需要耗费的最小体力。

Sample Input #1
10 10 6
##########
#......#.#
#####.#..#
#####...##
###.#.#.##
###.#.#..#
##...#..##
##.#..#.##
#...#....#
##########
1 1 1 1
3 6 1 3
3 6 6 3
2 8 2 5
2 5 2 8
7 4 6 2
Sample Output #1
30
測資資訊:
記憶體限制: 512 MB
不公開 測資點#0 (10%): 1.0s , <1K
不公開 測資點#1 (10%): 1.0s , <1M
不公開 測資點#2 (10%): 1.0s , <1M
不公開 測資點#3 (10%): 1.0s , <1M
不公開 測資點#4 (10%): 1.0s , <1M
不公開 測資點#5 (10%): 1.0s , <1M
不公開 測資點#6 (10%): 1.0s , <1M
不公開 測資點#7 (10%): 1.0s , <1M
不公開 測資點#8 (10%): 1.0s , <1M
不公開 測資點#9 (10%): 1.0s , <1M
Hint :

测试资料说明

占总分至少 30% 的测试资料中满足 5<= n, m <=30

占总分至少 40% 的测试资料中满足 0 <= Q <= 500

对于所有的测试资料,满足 5<= n, m <=250, 0 <= Q <= 50000 ,并且答案一定不会超过 2147483647 。

Tags:
出處:
2009海峽兩岸青少年程式設計競賽黃上恩 [管理者: tmt514(tomato) ]


ID User Problem Subject Hit Post Date
27426 811398(TAIWAN TOP) b237
169 2021-10-03 23:22