2 shunfurh shunfurh 于 2017.09.19 16:55 提问

Afshung Pizza Delivery

Description

Afshung-Pizza chain, a door-to-door pizza delivery service for Hamedung, a Sildavya district, needs your help for fastest possible pizza delivery plan. With a GIS device that shows all streets of the Hamedung, each delivery boy can find a fast route to deliver the pizza to the place of order. The Elyasung Company that sells and supports this GIS device needs your help to reprogram the device to provide even a faster route plan.

Hamedung is a rectangular shape district with many two-way streets that are all rectilinear. To show the map, the GIS device uses text characters as shown in the sample test data. In this format, each one kilometer of a street is shown by a dash (-) or a pipe (|) showing that the street is either in west-east or in north-south direction. A plus (+) on the map indicates a sharp 90 degree turn (with length zero) on that position without any traffic light. All such turns are marked with +. An intersection is shown by an integer τ on that position. τ is the timing of the traffic light at that intersection which can be either three or four way. To have a smooth and accident-free district, the municipality of Hamedung has forced that every traffic light has only one green light and two or three red lights for three or four intersections respectively. One of the lights in that intersection remains green for τ minutes (i.e., during [x, x + τ) time for some x) and others are red. In the next τ minutes, one other direction turns green as if the green light turns counter clockwise. This rule is observed in all intersections.

The time is set to zero at the beginning when the delivery boy starts moving. At this time, all traffic signals are set such that only the southern light (or the northern light if no southern light exists) of each intersection is set to green, and other lights at this intersection are set to red.

Note that the only positions that the driver can change his direction are: a turn (+), or an intersection (represented by a digit). As an example, if we have a pattern like -|- in the map, the driver cannot cross the pipe if he is moving from left to right or right to left, neither can he turn left or right, since there is no intersection at this location.

Given the complete map described above, the location of an Afshung-Pizza branch, marked by S, and the location of the final delivery place, marked by D, you are to write a program for GIS device to automatically find the fastest possible route to deliver pizza from S to D. Note the following assumptions:

S and D are parts of a street (replacing either a - or |)
S and D are not adjacent to any intersection or turn.
S and D are not adjacent to each other.
Intersections and/or turns are at least one kilometer apart.
'S', 'D', '+', and each digit have zero kilometer length.
Speed of delivery boy is one kilometer per minute.
Traffic that faces a green light can move in all directions. No straight move or turns are allowed at red light.
There is no traffic jam or other obstacles on the way.
Asterisk characters (*) show the border of the district.
Input

The first line of the input file contains a single integer t (1 <= t <= 10), the number of test cases, followed by the input data for each test case. The first line of each test case contains two integer numbers: N (1<= N <= 100) the number of rows of the map, and M (2 <= M <= 100) the number of columns of the map. Followed by the first line, there will be N lines, each containing a string of length M, consisting of '-', '|', '+', ' ', '*', 'S', 'D' or digits from '1' to '9'. Also, assume that the total number of intersections and turns (+) is at most 100.
Output

There should be one line in the output per test case containing a single number, the minimum time to drive from S to D, if there exists, otherwise the word impossible (with lower-case letters).
Sample Input

1
10 10


-D-3---+

  • | |*
  • | +-+*
  • |-| * *---4-1- *
  • | | *
  • | | * S--2-+ * ********* Sample Output

15

1个回答

caozhy
caozhy   Ds   Rxr 2017.10.04 23:54
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
Hoj 1020 Afshung Pizza Delivery
题目:http://acm.hit.edu.cn/hoj/problem/view?id=1020 这题写出来有一种畅快感。毕竟有一个Bug Debug了好久。  if((i == 0 || i == 2) && map[tempx][tempy] == '|') continue; 我写成了: if(i == 0 || i == 2 && map[tempx][tempy] == '|')
CodeChef November Challenge 2013 题解
最后得分是8.007分……比赛结束前3天还是并列rank5,结束前1天看了一下发现到rank8了……结束了一看到rank15了……简直吓尿了,会写计算几何/神数据结构的人咋这么多…… 下面题目按通过人数排序……由于CC这次有中文题面而且可以看到所有代码,就不讲题意也不贴代码了…… JOHNY:略。 MCHAIRS:答案就是2^n-1。 SDSQUARE:预处理出所有合法的数
1628 Pizza Delivery
1628 Pizza Delivery There is a pizza house located on a straight road, and there are many houses along the road which are customers to the pizza house. To attract more orders from his customers, the
Pizza V1.73 完美版+CX助手+pdg转PDF软件包
珍藏很久了,今天发布出来,大家分享! 这个应该是是最完美的软件包了,包含多个软件, 可以完成pdg的检查、解密、修复、转换等多种功能。 所以需要10分,。。。
Codeforces895A. Pizza Separation
A. Pizza Separation time limit per test 1 second memory limit per test 256 megabytes input standard input output standard output Students Vasya and Petya are studying at
PIZZA1.7.3破解版(解密所有超星的PDG文件格式).rar
PIZZA1.7.3破解版(解密所有超星的PDG文件格式) Pizza 解密超星66H、68H格式的pdg文件
Uva-1628 Pizza Delivery(机智DP)
题意:你是一个披萨店的老板,有一天突然收到了n个客户的订单(n 分析:这题有个特点就是如果ei-ti #include using namespace std; int t,T,n,p[105],e[105],f[105][105][2][105],vis[105][105][2][105]; int dfs(int l,int r,int op,int k
GETZ PIZZA – Home Delivery Management
GETZ PIZZA is a known pizza parlor批萨店 in the city. Looking at the increasing demand at workplaces and locality, we plan to extend the services to, Deliver@Home–free delivery within the city limits bas
工厂模式的生产披萨例子
定义简单工厂简单工厂其实不是一个设计模式,反而比较像是一种编程习惯。PizzaStore类,里面有orderPizza()方法。 这里是工厂的“客户”。PizzaStore现在通过SimplePizzaFactory取得比萨实例。SimplePizzaFactory类,里面有createPizza()方法。 这个创建方法通常声明为静态。 这个是建立比萨的“工厂”。Pizza里面有prepare
天上掉Pizza
题目描述 明明喜欢Pizza,但总是缺钱。有一天,他在报纸上阅读,他最喜爱的比萨饼店��必胜客,正在对大批新Pizza运行的促销。促销的办法是:在购买一些Pizza后,可能得到一些优惠券,可以对另一些Pizza进行打折,更令人惊喜的是这些优惠券可以结合起来。但是,有一个限制,Pizza必须一个接一个买,而后得到的优惠券也不可能追溯前面已经买过的Pizza。明明想尝试若干新品Pizza,可又没有充足