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 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.

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.

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

Source

```
//bfs+优先队列优化
//这里要求最小距离的最大值
#include
```
#include
#include
#include
#include
#include
using namespace std;
int d[31][31][31][31],dis[31][31][31][31];
struct node
{
int x1,y1,x2,y2,pre,id,mindist;
char m1,m2;
bool operator<(node t)const
{
return mindist Q;
s.pre=-1,tot=s.id=0;
Q.push(s);
way[tot++]=s;
while(Q.size())
{
node t=Q.top();
Q.pop();
if(str[t.x1][t.y1]=='s'&&str[t.x2][t.y2]=='S')
{
printf("%.2lfn",sqrt(1.0*d[t.x1][t.y1][t.x2][t.y2]));
stack st1,st2;
//t=way[t.pre];
while(t.pre!=-1)
{
if(t.m1!='*') st1.push(t.m1);
if(t.m2!='*') st2.push(t.m2);
t=way[t.pre];
}
while(st2.size())
{
putchar(st2.top());
st2.pop();
}
puts("");
while(st1.size())
{
putchar(st1.top());
st1.pop();
}
puts("");
return;
}
for(int i=0; i<4; ++i)
{
int x1=t.x1+dir[i][0],y1=t.y1+dir[i][1];
t.m1=move[i];
if(str[t.x1][t.y1]=='s') x1=t.x1,y1=t.y1,t.m1='*';
if(x1>=0&&x1=0&&y1=0&&x2=0&&y2d[x1][y1][x2][y2])
{
//记录下该路径
node x;
x.x1=x1,x.x2=x2,x.y1=y1,x.y2=y2,x.id=tot;
x.mindist=mi,x.pre=t.id,x.m1=t.m1,x.m2=t.m2;
way[tot++]=x;
Q.push(x);
d[x1][y1][x2][y2]=mi;
}
}
if(str[x1][y1]=='S') break;//这句话可以优化3倍的时间
}
}
}
}
}
int main()
{
while(~scanf("%d",&n)&&n)
{
for(int i=0; i

```
```

```
未经允许不得转载！poj1729(bfs+优先队列优化）
```