Morris' Blog 我在摸索我存在的意、生命的意、涵及值。 有真正神手般的害，套用模式是大部分的情。 那害的我存在的意何，托出神的存在？ 有候不能怪人不我，我已始省思， 什我有人的原因，而是全要靠人。 有候我我不同，那是因我做不到很多人能到的事情。 我不到、玩不起、得不明、理解得不多， 我缺少的文能力，就是一切一切能的判定。 此，我不得能做些人有助的事情。 我知道我自己是不服的性格，但在我不得不。 我有能力，因此我必。 我到底世界作什？充不定性， 而我是法出拔萃，想一般人似乎也回不了了。 越大的挑需要越力的支持，而我的支持是什？ 最近人，但都是失的局，人能接受， 不需要言，不需要通，一切所想都表不出。

49的鼓 6站台

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

输入的第一行包含三个正整数 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)

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

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 

30

测试资料说明

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

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

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