## 10923 - Seven Seas

Moderator: Board moderators

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

### 10923 - Seven Seas

I think I'm missing something in this problem. I saw dozens of people solved it in online contest but I find the problem unclear.
The enemy ships are pretty dumb, so that they will always move to the closest position they can get to you, ...
Consider the following situation at some portion of the board after my move:

Code: Select all

``````S..
..E

``````
Now where will the E move? There are two possibilities:

Code: Select all

``````SE.
...

OR,

S..
.E.

``````
Can someone please explain which one should we consider and why?

Dreamer#1
Learning poster
Posts: 77
Joined: Tue Oct 07, 2003 10:07 pm

liux0229
New poster
Posts: 8
Joined: Thu May 20, 2004 1:30 pm
Location: China
hi, Dreamer#1!
It was my post. Although I knew it was euclidean distance but I've kept getting WA since the contest. I was here for some hint on where could be wrong but only to find your post. Since you've got AC, can you post some input/output here?

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
not much......but u can try this.
input:

Code: Select all

``````7

........
........
........
.#E...E#
.#.....#
.#.....#
.#S....#
.#######
........

E......E
........
........
........
...S....
........
........
........
E......E

........
........
........
.#E...E#
.#.#.#.#
.#.###.#
.#S....#
.#######
........

........
...#....
........
..#.....
........
........
..S.....
........
........

........
.E.#....
...E....
..#.....
........
........
..S.....
........
........

........
.E.E....
...S....
.E..E...
........
........
........
........
........

E......#
........
........
........
........
........
........
.......S
#.......

``````
output:

Code: Select all

``````I'm the king of the Seven Seas!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
Oh no! I'm a dead man!
Oh no! I'm a dead man!
``````
Jalal : AIUB SPARKS

liux0229
New poster
Posts: 8
Joined: Thu May 20, 2004 1:30 pm
Location: China
Sorry, it was me

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm
is the soln a straight forward BFS?? but 8^10 is much bigger (in worst case) nay kinda huristic needed??
Self judging is the best judging!

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of
shanto86 wrote:is the soln a straight forward BFS?? but 8^10 is much bigger (in worst case) nay kinda huristic needed??

no, wise DFS (recursive) is enough.
Sorry For My Poor English..

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
Hello there!

I have got correct answers for all the inputs of this board, but I get WA from OJ.

Could anyone say me if are there some tricky inputs?
And, could anyone say me if is this correct?

input:

Code: Select all

``````8
.....S..
........
........
########
E......E
........
....E...
........
EEE.....

.....S..
........
........
........
E......E
........
....E...
........
..E.....

.....S..
........
........
........
........
........
........
E......E
........

.....S..
........
........
........
E......E
........
........
........
........

.....S..
........
........
........
........
E......E
........
........
........

E....S..
........
........
........
........
........
....E...
........
EEE.....

.....S..
........
........
........
........
..E.....
....E...
........
........

.....S..
........
.....#..
........
........
..E.....
....E...
........
........
``````
output:

Code: Select all

``````I'm the king of the Seven Seas!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
Oh no! I'm a dead man!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
``````

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
My output:

Code: Select all

``````I'm the king of the Seven Seas!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
I'm the king of the Seven Seas!
Oh no! I'm a dead man!
I'm the king of the Seven Seas!``````
No trick at all. A simple DFS will do.

[EDIT:] Please ignore my output, it's wrong and Emilio's output is correct.
Last edited by Cho on Sat Oct 08, 2005 9:02 am, edited 2 times in total.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
Hi another time!

I can't figure out how you can destroy the enemies in the fourth case without dead.
Could you explain me that?

little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm
Strange, my program gives the same answers as Emilio's.
I'd be interested how the ship can escape in cases 4 and 6.

krijger
New poster
Posts: 39
Joined: Wed Jul 21, 2004 12:35 am
My AC program also gives the same answers as Emilio's.

btw. In case 4 you can escape if you allow the ship to go 'outside the area', but I don't see how you can escape in case 6.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
Thanks!

I have got AC. My trouble was a bug in my code.

But I have got AC with different approachs:
1. I calculate the distance how euclidean distance.
2. I calculate the distance how Manhattan distance.
3. I can move (only test with my own ship) where there is a rock.
4. I can't move (only test with my own ship) where there is a rock.
5. A mixture of them.

Strange?

I think test cases are poor or other things...

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
There is a bug in my previously AC-ed code, so the output of my previous post is wrong.

Solaris
Learning poster
Posts: 99
Joined: Sun Apr 06, 2003 5:53 am
Contact:

### 10923 - Seven Seas

This code runs ok in my VC 6.0 but shows CE in the OJ ... I have removed the sort function and then the CE is removed. Can any one tell me why this happens ?? (I have overloaded the < operator, and this should run ok, I want to know why not)

Code: Select all

``````You do not want to get AC in 1.5 seconds in this problem
``````

I have already got AC in this problem by omitting the sort function. But I am surprised to see some near zero second solves in this problem. Is there any greedy approach (or any other approach than DFS) to solve this problem ?? Thanx in advance for any hint that anyone can give.