2 shunfurh shunfurh 于 2017.09.10 10:01 提问

The Erythea Campaign

O' mighty warrior,

Thy mission is to slay the foul king of Erythea.
Thou shall find him in his realm in the south.

God bless you,
King of Isladia.
After reading the order, you know you have a long, dangerous way down to the south, to find the king of Erythea in his realm and kill him. The Erythea realm is a rectangular region, with a number of horrible strongholds in it. Impenetrable walls enclose the region, so the only way for you to enter the realm is to fly by your Pegasus (flying horse) and land in some point in the region. The hiding place of the king is known so you just need to find your way to that location. As the area is extensive and covered by different terrain types, you have to travel on the grid-like roads in the region. The problem is, there are many guards on the towers of strongholds who can see you, and once seen, you have no chance to see your family again! The closer you travel to the strongholds, the greater the chances to be seen by the guards. The problem is to find the safest way from the point your Pegasus lands to the point where the king is.

More abstractly, you have an m X n grid with squares of the same size, denoting the realm and the roads in it. You can travel along the lines in the grid (roads), and at each intersection (road crossing) you may turn into another road. Assume each stronghold comprises a set of adjacent squares of the grid (Figure 1). As you cannot enter a stronghold, your path never intersects the interior of a stronghold, yet you can travel on a road which is on stronghold boundaries (Figure 2). Suppose you can land your Pegasus exactly on a road crossing (the source point - S in Figure 1) and the hiding place of the king is on another road crossing (the destination point - D in Figure 1). Neither of these points lie inside a stronghold but may be placed on a stronghold boundary (as D does in Figure 1). Each road crossing is assigned a risk level which depends on the shortest road distance from the crossing to a point of the grid which is on the boundary of a stronghold. For a road crossing with the shortest road distance d to a boundary of strongholds, the risk level equals to m + n - d (Figure 3). It is assumed that there is at least one stronghold in the region, so that the definition of risk level is well-defined. The problem is, given the region's map and the source and destination points, find the path from the source to the destination which lies on the grid lines, so that sum of the risk levels of the points on the path (including source and destination) be minimum. As stated before, the path cannot intersect the interior of a stronghold.

Input

The input file consists of several test cases. The first line of the file contains a single number M, which is the number of test cases in the file (1 <= M <= 10). The rest of the file consists of the data of the test cases. Each test case data begins with a line containing the number of rows and the number of columns in the grid, which are in the range 1 to 80. The second line of a test case contains two pairs of integers, which are y and x coordinates of the source point (where the Pegasus landed) and the y and x coordinates of the destination point (where you may find the king). The horizontal and vertical lines in the grid are indexed from left to right and top to bottom from 0, so the coordinates can be expressed using these indices.

Following the first two lines, there are lines that describe the map of the region. Each line consists of a string of 0's and 1's, describing squares of the corresponding row. A 1 in the string tells you that the corresponding square in the grid belongs to a stronghold. The width of the region is the length of all strings, and its height in the number of strings.

Output

The output for each test case is the total risk of the minimum risk path from the landing point to the destination. Recall that the total risk of a path is sum of the risk levels of the points in the path (including source and destination). If no path exists between source and destination, the output should be 'no solution'. The output for each test case must be written on a separate line.

Sample Input

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

Sample Output

149
101

1个回答

devmiao
devmiao   Ds   Rxr 2017.09.27 21:52
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
ZOJ1430 POJ1697 The Erythea Campaign
/******************************************************************************* # Author : Neo Fung # Email : neosfung@gmail.com # Last modified: 2011-11-06 21:50 # Filename: ZOJ1430 POJ1697 The
ZOJ 1430 The Erythea Campaign(最短路)
普通的最短路算法都可以. 边算边判断能否连通. #include #include #include #include #include #include #include #define pii pair using namespace std; const int maxn = 81; char grid[maxn][maxn]; bool inq[maxn * maxn]
ZOJ 1430 / POJ 2679 The Erythea Campaign (bfs+dijkstra)
<br />繁,但是不难。<br /> <br />首先,建图,题中给出的是m*n的矩阵,里面包含了所有stronghold的分布,但是你需要把他转换成一个图。但是路径不能穿过堡垒,多以说两个堡垒之间的两个点不能相互到达。还有就是每个点应该保存它可以到达的点的信息,当使用dijkstra求最短路径的时候,这些点可以当邻接表使用,很方便的。<br /> <br />接下来是每个的危险值,求法是m+n-d,不会出现负值。d的意思是它到达离他最近的堡垒的距离。对于每个堡垒上的点做bfs求出所有点到他的最短距离,如
zoj 1430 || poj 1697 The Erythea Campaign
<br />最短路分类里的,zoj只有50个人过,暴汗,不过应该大多数是被冗长的题目给吓住了吧。<br /> <br />给你地图,图中的1代表这里有根据地,你越靠近根据地,越容易被敌人发现,危险等级越高。不能从根据地中间穿过。<br /> <br />给你起点,终点,求最少的危险等级和使之可以到达,如果没有 输出,no solution。<br /> <br />危险等级是这么定义的,你在某个点,这个点离它最近的根据地的距离为d,那么,这个点的危险等级就是,矩阵的长+宽-d。<br /> <br />我第
Salesforce Marketing功能简介(VI)
前言 在市场营销领域, 营销活动(Campaign)是一个对外的市场推广项目,你需要规划、管理和和跟踪。营销活动的类型多种多样。传统的方法包括广告、研讨会(seminar)和商业展览。新的在线技术带来了新的手段,比如在线研讨会(Webinar)、Email、SEM和社交媒体,通过这些手段能直接联系到潜在客户。   下图展示了一个理想化的市场和销售流程.   首先是市场部门创建和开展营
Siesta行动:一起新发现的定向攻击
过去几周时间里,趋势科技收到几份利用各种应用版本漏洞窃取各类组织信息的报告,与Safe行动相似,这些行动进行的非常隐蔽。并将攻击者精心策划的这起定向攻击称为Siesta行动,其目标为能源、金融、医疗保健、媒体通信及交通运输等等固定的产业。 随后fireeye对此活动展开更详细的分析,fireeye表示此活动和APT1有关联,他们发现二零一四年二月二十〇日针对客户在电信部门,利用鱼叉式网络钓鱼邮件
Android广告量监控的技术实现(campaign measurement)
有这么一种需求,我们找广告平台来推销我们的APP,我们想要知道这个广告平台的转化率到底怎么样。是否可以做到?如果APP是发布在Google Play的话,那么是可以做到的。当用户点击一条广告,并跳转进了Google Play,Google Play可以获取到广告的链接,而这条链接里带有referrer参数的话,referrer参数里的内容将在APP安装完之后,就发给APP。如果APP有监听这个广播的
Agri-Net (POJ 1258)
Description Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.  Farmer John or
POJ_1258_Farmer John has been【基础最小生成树】
Time Limit:1000MS     Memory Limit:10000KB     64bit IO Format:%I64d & %I64u Submit Status Description Farmer John has been elected mayor of his town! One of his campaign promises was to bring in
campaign brief
unica campaign brief