Page 1 of 2

10923 - Seven Seas

Posted: Sat Oct 01, 2005 6:06 pm
by Dreamer#1
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?

Thanks in advance. :)

Posted: Sun Oct 02, 2005 3:02 am
by Dreamer#1
sorry i forgot to login... :D

Posted: Sun Oct 02, 2005 5:52 am
by liux0229
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?

Posted: Sun Oct 02, 2005 9:25 pm
by CodeMaker
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!

Posted: Mon Oct 03, 2005 11:58 am
by liux0229
Sorry, it was me

Posted: Wed Oct 05, 2005 9:20 am
by shanto86
is the soln a straight forward BFS?? but 8^10 is much bigger (in worst case) nay kinda huristic needed??

Posted: Wed Oct 05, 2005 9:29 am
by wook
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.

Posted: Thu Oct 06, 2005 10:44 pm
by Emilio
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!
Thanks in advance!

Posted: Fri Oct 07, 2005 3:17 am
by Cho
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.

Posted: Fri Oct 07, 2005 8:16 pm
by Emilio
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?

Posted: Fri Oct 07, 2005 10:14 pm
by little joey
Strange, my program gives the same answers as Emilio's.
I'd be interested how the ship can escape in cases 4 and 6.

Posted: Fri Oct 07, 2005 10:50 pm
by krijger
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.

Posted: Sat Oct 08, 2005 1:52 am
by Emilio
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...

Posted: Sat Oct 08, 2005 8:59 am
by Cho
There is a bug in my previously AC-ed code, so the output of my previous post is wrong.

10923 - Seven Seas

Posted: Mon Feb 06, 2006 10:10 am
by Solaris
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.

Perdon my bad english :P