#P1697. The Erythea Campaign
The Erythea Campaign
题目描述
你的使命是斩杀艾瑞西亚的暴君。
你将在南方的领土找到他。
愿神保佑你,
伊斯拉迪亚国王。
接到命令后,你需要长途跋涉前往南方,在艾瑞西亚的领土中找到国王并将其消灭。艾瑞西亚领土是一个矩形区域,分布着许多恐怖的要塞。区域被不可逾越的城墙包围,因此你只能骑乘飞马降落在区域内的某个点。国王的藏身之处已知,你只需找到前往该地点的路径。由于该区域广阔且地形复杂,你必须沿着网格状的道路行进。问题在于,要塞的塔楼上有许多守卫会发现你,一旦被发现就必死无疑!你离要塞越近,被守卫发现的几率就越大。问题是要找到从飞马降落点到国王藏身之处的最安全路径。
更抽象地说,你有一个的网格,每个格子代表领土和道路。你可以沿着网格线(道路)移动,在每个交叉点(路口)可以转向其他道路。每个要塞由一组相邻的网格格子组成(图)。由于不能进入要塞内部,你的路径不能穿过要塞的内部,但可以沿着要塞的边界道路行进(图)。假设飞马降落点(起点)和国王藏身点(终点)均位于路口,且不在要塞内部,但可能位于要塞边界(如在图中)。每个路口的风险等级由该路口到最近要塞边界的最短道路距离决定。对于距离为的路口,其风险等级为(图)。假设区域内至少有一个要塞,因此风险等级的定义是明确的。给定区域地图、起点和终点,找出沿网格线的路径,使得路径上所有点(包括起点和终点)的风险等级之和最小。路径不能穿过要塞内部。
图. 区域。可沿网格线(包括边界线)移动,阴影格子为要塞。
图. () 允许沿要塞边界移动;() 禁止穿过要塞内部。
图. 网格中的点到要塞的距离为,到要塞的距离为,风险等级为。
输入
输入包含多个测试用例。第一行是测试用例数()。每个测试用例的第一行是网格的行数和列数(范围到)。第二行包含两对整数,表示起点(飞马降落点)和终点(国王藏身点)的和坐标。网格的水平和垂直线从左到右、从上到下编号为,因此坐标可用这些索引表示。
接下来是网格地图的描述。每行是一个由和组成的字符串,表示对应行的格子。表示该格子属于要塞。网格的宽度是字符串的长度,高度是字符串的数量。
输出
每个测试用例输出一行,包含起点到终点的最小风险路径的总风险。若无法到达,输出" "。
输入数据1
2
8 6
1 5 7 1
000000
011000
001000
000110
000110
000010
111000
000000
5 5
4 0 1 5
10000
10000
11111
00011
00001
输出数据1
149
101
提示
第一个测试用例对应图的情况。
来源
德黑兰1999竞赛