2 shunfurh shunfurh 于 2017.09.07 13:32 提问

Jack and Jill

Ever since the incident on the hill, Jack and Jill dislike each other and wish to remain as distant as possible. Jack and Jill must attend school each day; Jack attends a boys' school while Jill attends a girls' school. Both schools start at the same time. You have been retained by their lawyers to arrange routes and a schedule that Jack and Jill will adhere to so as to maximize the closest straight-line distance between them at any time during their trip to school.

Jack and Jill live in a town laid out as an n by n square grid (n <= 30). It takes 1 minute to walk from one location to an adjacent location. In maximizing the distance between Jack and Jill you need consider only the distance between the locations they visit (i.e. you need not consider any intermediate points on the path they take from grid location to grid location). Some locations are impassable due to being occupied by rivers, buildings, etc. Jack must start at his house and walk continuously until he gets to school. Jill must start at her house at the same time as Jack and walk continuously until she arrives at her school. Jack's house and school are impassable to Jill while Jill's house and school are impassable to Jack. Other grid locations that are impassable to both Jack and Jill are given in the input.

Input

Input will consist of several test cases. Each test case will consist of n, followed by n lines with n characters representing a map of the town. In the map, Jack's house is represented by 'H', Jack's school is represented by 'S', Jill's house is represented by 'h', Jill's school is represented by 's', impassable locations are represented by '*', and all other locations are represented by '.' You may assume the normal cartographic convention that North is at the top of the page and West is to the left. A line containing 0 follows the last case.

Output

For each input case you should give three lines of output containing:

the closest that Jack and Jill come during the schedule (to 2 decimal places)
Jack's route
Jill's route.
Each route is a sequence of directions that Jack or Jill should follow for each minute from the start time until arriving at school. Each direction is one of 'N', 'S', 'E', or 'W'. If several pairs of routes are possible, any one will do. You may assume there is at least one solution. Leave a blank line between the output for successive cases.

Sample Input

10
..........
...H......
.**...s...
.**.......
.**.......
.**.......
.**.......
.**.......
...S..h..*
..........
0

Sample Output

6.71
WWWSSSSSSSEEE
NEEENNNNNWWW

1个回答

caozhy
caozhy   Ds   Rxr 2017.09.23 08:56
已采纳
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
[Android]Jack和Jill的阴暗面
Jack & Jill Android新编译工具链
poj 1729 Jack and Jill (比较有特色的bfs)
Description Ever since the incident on the hill, Jack and Jill dislike each other and wish to remain as distant as possible. Jack and Jill must attend school each day; Jack attends a boys’ school whil
Android 新一代编译 toolchain Jack & Jill 简介
2016 年 3 月 10 日, Google 向外界发布了 Android N 的预览版,并宣布了 Android N 的Roadmap,Android N 的最终版源代码将于今年 8 或 9 月份释出到 AOSP 项目。 在众多的 Android N 新特性中,有一项新工具链的出现与 Android 生态圈的所有开发者息息相关,即 Jack & Jill 编译器的引入。 在依赖
Android最新编译工具Jack和Jill
前几天在编译Android6.0系统的时候,报了一个ERROR: Security problem, see Jack server log的错误,就顺便查了一些资料,简单了解了一下Jack并总结如下: 介绍Jack之前,我们先了解一下在Jack未诞生之前我们使用的Javac和dx工具。 对于Java(非Android)应用,我们只需要Java编译器(javac)。它可以
POJ1729 Jack and Jill (双向广度优先搜索, DBFS)
loading
poj1729(bfs+优先队列优化)
Jack and Jill Time Limit: 3000MS   Memory Limit: 65536K Total Submissions: 1502   Accepted: 390   Special Judge Description Ever since the incident on the hill, Jack an
jack server
This documentation describes usage of Jack server 1.3-a11. Jack server The Jack server's goal is to handle a pool of Jack compiler instances in order to limit memory usage and benefit from alrea
Android 错误总结
一、 Error:Execution failed for task ‘:app:transformClassesWithPreJackPackagedLibrariesForDebug’. com.android.build.api.transform.TransformException: com.android.jack.api.ConfigNotSupportedException:
POJ 1729 Jack and Jill BFS *
题目地址:http://poj.org/problem?id=1729 本来想用string保存路程 后来发现太慢了 优先队列要以一条路中最近的距离排序 #include #include #include #include #include #include using namespace std; const int maxn=30+5; const double INF=9999999
主数据管理的Jill Dyche, Evan Levy六层次模型
MDM实际上是现代企业进行日常经营的非常重要的基础信息,企业的几乎所有生产经营活动,都离不开主数据的支持,因此,主数据是最重要的企业信息之一。但是,针对MDM的管理,尤其是MDM系统的建设,目前尚未有一套类似SOA参考架构之类的参考模型出来,往往会对准备建设MDM或进行MDM管理的企业或者CIO们,带来一定的困惑,近日查看相关资料发现,Jill Dyche, Evan Levy的主数据层次模型,对