#P1697. The Erythea Campaign

The Erythea Campaign

题目描述

你的使命是斩杀艾瑞西亚的暴君。

你将在南方的领土找到他。

愿神保佑你,

伊斯拉迪亚国王。

接到命令后,你需要长途跋涉前往南方,在艾瑞西亚的领土中找到国王并将其消灭。艾瑞西亚领土是一个矩形区域,分布着许多恐怖的要塞。区域被不可逾越的城墙包围,因此你只能骑乘飞马降落在区域内的某个点。国王的藏身之处已知,你只需找到前往该地点的路径。由于该区域广阔且地形复杂,你必须沿着网格状的道路行进。问题在于,要塞的塔楼上有许多守卫会发现你,一旦被发现就必死无疑!你离要塞越近,被守卫发现的几率就越大。问题是要找到从飞马降落点到国王藏身之处的最安全路径。

更抽象地说,你有一个m×nm \times n的网格,每个格子代表领土和道路。你可以沿着网格线(道路)移动,在每个交叉点(路口)可以转向其他道路。每个要塞由一组相邻的网格格子组成(图11)。由于不能进入要塞内部,你的路径不能穿过要塞的内部,但可以沿着要塞的边界道路行进(图22)。假设飞马降落点(起点SS)和国王藏身点(终点DD)均位于路口,且不在要塞内部,但可能位于要塞边界(如DD在图11中)。每个路口的风险等级由该路口到最近要塞边界的最短道路距离决定。对于距离为dd的路口,其风险等级为m+ndm + n - d(图33)。假设区域内至少有一个要塞,因此风险等级的定义是明确的。给定区域地图、起点和终点,找出沿网格线的路径,使得路径上所有点(包括起点和终点)的风险等级之和最小。路径不能穿过要塞内部。

11. 8×68×6区域。可沿网格线(包括边界线)移动,阴影格子为要塞。

22. (aa) 允许沿要塞边界移动;(bb) 禁止穿过要塞内部。

33. 5×65×6网格中的点PP到要塞AA的距离为33,到要塞BB的距离为22,风险等级为5+62=95+6-2=9

输入

输入包含多个测试用例。第一行是测试用例数MM1M101 \leq M \leq 10)。每个测试用例的第一行是网格的行数和列数(范围118080)。第二行包含两对整数,表示起点(飞马降落点)和终点(国王藏身点)的yyxx坐标。网格的水平和垂直线从左到右、从上到下编号为00,因此坐标可用这些索引表示。

接下来是网格地图的描述。每行是一个由0011组成的字符串,表示对应行的格子。11表示该格子属于要塞。网格的宽度是字符串的长度,高度是字符串的数量。

输出

每个测试用例输出一行,包含起点到终点的最小风险路径的总风险。若无法到达,输出"nono solutionsolution"。

输入数据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

提示

第一个测试用例对应图11的情况。

来源

德黑兰1999竞赛