题目描述(ID:12386)
标题: 设计迷宫
标签:
详情:
长假过后,迷宫设计大师必须完成他的工作。旅游公司给他一张矩形的地图。地
图由N*M个小方块组成。旅游公司将把一对夫妇放在迷宫中的两个不同的小方块
上,让他们互相寻找。
原本的地图上是空旷旷的一片,大师要做的就是在一些小方块之间建造一些墙从
而把地图变成迷宫。建造的迷宫有一个条件,无论这对夫妻出现在何处,他们之
间只有且仅有一条路。
这对他来说并不困难,但他是一个善解人意的人。他也知道在两个相邻广场之间
建造每面墙的成本是不同的。所以他想设计一个迷宫,让旅游公司花费最少的钱
来建造它并满足上诉条件。
建成迷宫后,你得到了 Q 个询问包含夫妻两人将被放置的位置信息。你需要弄
清楚它们之间最短路径的长度(一个小方格为一个单位)。
输入格式:
输入的第一行包含两个整数N和M。 
接下来输入的N×M行给出迷宫中每个小方块的信息,它们的信息按顺序输入,
输入顺序为 (1,1),(1,2),(1,3)…(1,m)(2,1)(2,2)(2,3)…(3,1)……(n,m) 每行包含两个字符 D和R和两个整数,D后面的整数代表建造该小方格下边的墙
的花费,R后面的整数代表建造该小方格右边的墙的花费。如果边是边界,缺少
的路径将被替换为X 0。 
下一行包含一个整数 Q表示有Q个询问。 
接下来q行,每一行两个整数对(x1,y1)(x2,y2)代表夫妻两人的位置坐标。 
输入数据保证满足条件的只有一种迷宫(即答案唯一)。
输出格式:
对于每个问题,输出一行,其中一个整数表示两个给定方块之间最短路径的长度
限制: 对于30%的数据: 0<=N,M<=5
对于100%的数据:0<=N,M<=500
样例:

输入

3 3
D 1 R 9
D 7 R 8
D 4 X 0
D 2 R 6
D 12 R 5
D 3 X 0
X 0 R 10
X 0 R 11
X 0 X 0
3
1 1 3 3
1 2 3 2
2 2 3 1

输出

4
2
2
登录并解答